强连通分量算法（Tarjan's Strongly Connected Component Algorithm)
利用深度优先算法找到一个非强连通的有向图中的所有强连通子图。无向图可以被认为是同时具备u->v和v->u的图。
一些概念
-
强连通：在有向图中，任意点u与v之间存在有来回两个方向的通路，类似存在一个环；
-
强连通图：图中任意两点存在强连通；
-
强连通分量：图中存在强连通的子图；
-
DFN(u)：定义为第一次访问点u时的时间戳；
-
LOW(u)：定义为u或u的子树能够回溯到的最早的栈中节点的DFN(u)。
思路
当dfn[u] = low[u]时，以u为根的子树上所有节点是一个强连通分量。
-
首次访问某点u时，令low[u] = dfn[u] = index(or time)（初始化）
-
每到达一个点u，将其入栈（dfs的内容）
-
遍历所有与点u相连的点v：
-
若v不在栈中（树枝边）即未被访问过，递归方法继续往v后面搜索（如dfs()/tarjan())，最终会得出新的low[v]；即low[u]=min(low[u], low[v])；
-
若v在栈内即已被访问，通过比较low[u]和v第一次被访问时的序列号/次数，来更新low[u]，即low[u] = min(low[u], dfn[v])。
-
图解（来自史上最清晰的Tarjan算法详解-segementFault）
强连通分量：[{0,1,2,3},{4},{5}]
第一步：从节点0开始
-
首先访问 0 -> 2 -> 4 -> 5并将其加入栈。根据访问顺序标记为1至4。这里也可以从0往1走。
-
对于节点5（栈内第一个元素），没有后续的节点了，检查到dfn[5] = low[5] = 4，所以退栈，得{5}为一个强连通分量。
第二步：返回节点4
-
节点4只有一个子树（节点5，已退栈），因此low[4] = min(low[4], low[5]) = low[4] = 3。
-
节点4后无其他子节点，且low[4] = dfn[4]，退栈，得到第二个强连通分量。
第三步：返回节点2，并访问节点3及其子树
-
low[2] = min(low[2], low[4]) = 2，节点4（已出栈）是其中一个子节点， 节点2仍有后续子节点；
-
继续探索节点2的另一个子节点3。节点3入栈，初始化dfn[3] = low[3] = 5；
-
发现节点3有通向节点0的路径，且节点0仍在栈中，有low[3] = min(low[3], dnf[0]) = 1；
-
发现节点3有通向节点5的路径，但5已退栈，无需更新low[3]。
第四步：从节点3返回节点2
-
根据刚刚得到的新low[3]更新low[2] = min(low[2], low[3]) = 1；
-
节点2无其他后续子节点，返回0
第五步：返回节点0，并访问节点1及其子树
-
根据low[2]更新low[0]，low[0] = min(low[0], low[2]) = 1;
-
发现节点1，dfn[1] = low[1] = 6;
-
发现后续节点3且3还在栈内，low[1] = min(low[1], dfn[3]) = 5
第六步：返回节点0
- dfn[0] = low[0] = 1, 退栈至0，得
伪代码
void tarjan(int u) {
++index;
dfn[u] = low[u] =index; // 节点u的初始值
stack.push(u); // 入栈
for (auto& e : edges[u]) { // 遍历与u相连的点
if (!visited[e]) { // 若e未被访问过
tarjan(e); // 继续向下找其子节点
low[u] = min(low[u], low[v]);
}
else if (e is in stack) { // 若e被访问过且还在栈内
low[u] = min(low[u], dfn[e]);
}
}
if (dfn[u] == low[u]) { // 遍历完所有子节点后，检查是否相等
while (!stack.empty()) { // 循环退栈并打印
v = stack.pop();
print v;
}
}
}