Tarjan 强连通算法
定义
-
1、有向图 G 中，以顶点 v 为起点的弧的数目称为 v 的出度，记做 deg+（v）；以顶点 v 为终点的弧的数目称为 v 的入度，记做 deg-（v）。
-
2、如果在有向图 G 中，有一条<u，v>有向道路，则 v 称为 u 可达的，或者说，从 u 可达 v。
-
3、如果有向图 G 的任意两个顶点都互相可达，则称图 G 是强连通图，如果有向图 G 存在两顶点 u 和 v 使得 u 不能到 v，或者 v 不能到 u，则称图 G 是强非连通图。
-
4、如果有向图 G 不是强连通图，他的子图 G2 是强连通图，点 v 属于 G2，任意包含 v 的强连通子图也是 G2 的子图，则乘 G2 是有向图 G 的极大强连通子图，也称强连通分量。
-
5、什么是强连通？强连通其实就是指图中有两点 u，v。使得能够找到有向路径从 u 到 v 并且也能够找到有向路径从 v 到 u，则称 u，v 是强连通的。
定义的理解
既然我们现在已经了解了什么是强连通，和什么是强连通分量，可能大家对于定义还是理解的不透彻，我们不妨引入一个图加强大家对强连通分量和强连通的理解：
标注棕色线条框框的三个部分就分别是一个强连通分量，也就是说，这个图中的强连通分量有 3 个。
其中我们分析最左边三个点的这部分：
其中 1 能够到达 0,0 也能够通过经过 2 的路径到达 1，1 和 0 就是强连通的。
其中 1 能够通过 0 到达 2,2 也能够到达 1，那么 1 和 2 就是强连通的。
…………………
同理，我们能够看得出来这一部分确实是强连通分量，也就是说，强连通分量里边的任意两个点，都是互相可达的。
那么如何求强连通分量的个数呢？另外强连通算法能够实现什么一些基本操作呢？我们继续详解。
Tarjan 算法详解
接着我们开始接触算法，讨论如何用 Tarjan 算法求强连通分量个数：
Tarjan 算法，是一个基于 Dfs 的算法（如果大家还不知道什么是 Dfs，自行百度学习），假设我们要先从 0 号节点开始 Dfs，我们发现一次 Dfs 我萌就能遍历整个图（树），而且我们发现，在 Dfs 的过程中，我们深搜到了其他强连通分量中，那么俺们 Dfs 之后如何判断他喵的哪个和那些节点属于一个强连通分量呢？我们首先引入两个数组：
①dfn[]
②low[]
第一个数组 dfn 我们用来标记当前节点在深搜过程中是第几个遍历到的点。第二个数组是整个算法核心数组，我们稍后再说，这个时候我们不妨在纸上画一画写一写，搞出随意一个 Dfs 出来的 dfn 数组来观察一下（假设我们从节点 0 开始的 Dfs，其中一种可能的结果是这样滴）：
这个时候我们回头来看第二个数组要怎样操作，我们定义 low[u]=min(low[u]，low[v]（即使 v 搜过了也要进行这步操作，但是 v 一定要在栈内才行）)，u 代表当前节点，v 代表其能到达的节点。这个数组在刚刚到达节点 u 的时候初始化：low[u]=dfn[u]。然后在进行下一层深搜之后回溯回来的时候，维护 low[u]。如果我们发现了某个节点回溯之后的 low[u]值还是==dfn[u]的值，那么这个节点无疑就是一个关键节点：从这个节点能够到达其强连通分量中的其他节点，但是没有其他属于这个强连通分量以外的点能够到达这个点，所以这个点的 low[u]值维护完了之后还是和 dfn[u]的值一样，口述可能理解还是相对费劲一些，我们走一遍流程图：
-
① 首先进入 0 号节点，初始化其 low[0]=dfn[0]=1，然后深搜到节点 2，初始化其：low[2]=dfn[2]=2，然后深搜到节点 1，初始化其：low[1]=dfn[1]=3；
-
② 然后从节点 1 开始继续深搜，发现 0 号节点已经搜过了，没有继续能够搜的点了，开始回溯维护其值。low[1]=min（low[1]，low[0]）=1；low[2]=min（low[2]，low[1]）=1；low[0]=min（low[0]，low[2]）=1；
-
③ 这个时候猛然发现，low[0]==dfn[0]，这个时候不要太开心，就断定一定 0 号节点是一个关键点，别忘了，这个时候还有 3 号节点没有遍历，我们只有在其能够到达的节点全部判断完之后，才能够下结论，所以我们继续 Dfs。
-
④ 继续深搜到 3 号节点，初始化其 low[3]=dfn[3]=4，然后深搜到 4 号节点，初始化其：low[4]=dfn[4]=5，这个时候发现深搜到底，回溯，因为节点 4 没有能够到达的点，所以 low[4]也就没有幸进行维护即：low[4]=dfn[4]（这个点一定是强连通分量的关键点，但是我们先忽略这个点，这个点没有代表性，一会分析关键点的问题），然后回溯到 3 号节点，low[3]=min（low[3]，low[4]）=4；发现 low[3]==dfn[3]那么这个点也是个关键点，我们同样忽略掉。
-
⑤ 最终回溯到节点 0，进行最后一次值的维护：low[0]=min（low[0]，low[3]）=0，这个时候我们猛然发现其 dfn[0]==low[0]，根据刚才所述，那么这个点就是一个关键点：能够遍历其属强连通分量的点的起始点，而且没有其他点属于其他强连通分量能够有一条有向路径连到这个节点来的节点。
※※大家仔细理解一下这句话，因为这个点属于一个强连通分量，而且强连通分量中的任意两个节点都是互达的，也就是说强连通分量中一定存在环，这个最后能够回到 0 号节点的 1 号节点一定有机会维护 low[1]，因为 0 号节点是先进来的，所以其 low[1]的值也一定会跟着变小，然后在回溯的过程中，其属一个强连通分量的所有点都会将 low[u]值维护成 low[0]，所以这个 0 号节点就是这个关键点：能够遍历其属强连通分量的起始点而且这样的起始点一定只有一个，所以只要发现了一个这样的关键起始点，那么就一定发现了一个强连通分量。而且这个节点没有其他点属于其他强连通分量能够有一条有向路径连到这个节点来的节点：如果这样的点存在，那么这些个点应该属于同一个强连通分量。
那么综上所述，相信大家也就能够理解为什么 dfn[u]==low[u]的时候，我们就可以判断我们发现了一个强连通分量了。
代码示例
#include <cstdio>
#include <stack>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, idx = 0, k = 1, number = 0;
int head[100]; //用于链式前向星
int ins[100] = {0};
int dfn[100] = {0}, low[100] = {0};
int Belong[100]; //染色，每个强连通分量一个颜色
stack<int> s;
struct edge
{
int v, next;
} e[100];
void add(int u, int v)
{
e[k].v = v;
e[k].next = head[u];
head[u] = k++;
}
void readdata()
{
int a, b;
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &a, &b);
add(a, b);
}
}
void tarjan(int u)
{
int v;
dfn[u] = low[u] = ++idx; //每次dfs，u的次序号增加1
s.push(u); //将u入栈，栈就是为了回溯染色
ins[u] = 1; //标记u在栈内
for (int i = head[u]; i != -1; i = e[i].next)
{
//访问从u出发的边
v = e[i].v;
if (!dfn[v])
{
//如果v没被处理过
tarjan(v); //dfs(v)
low[u] = min(low[u], low[v]); //u点能到达的最小次序号是它自己能到达点的最小次序号和连接点v能到达点的最小次序号中较小的
}
else if (ins[v])
low[u] = min(low[u], dfn[v]); //如果v在栈内，u点能到达的最小次序号是它自己能到达点的最小次序号和v的次序号中较小的
}
if (dfn[u] == low[u])
{
//回溯，对该强连通分量内的点染色
number++;
do
{
v = s.top();
s.pop();
ins[v] = 0;
Belong[v] = number;
} while (u != v);
}
}
void work()
{
for (int i = 1; i <= n; i++)
if (!dfn[i])
tarjan(i);
printf("\n");
printf("共有%d强连通分量，它们是:\n", number);
for (int i = 1; i <= number; i++)
{
printf("第%d个:", i);
for (int j = 1; j <= n; j++)
{
if (Belong[j] == i)
printf("%d ", j);
}
printf("\n");
}
}
int main()
{
readdata();
work();
return 0;
}