其中有Tarjan算法的正确性证明。
对求有向图强连通分量的tarjan算法原理的一点理解by naturerun
讲解视频：形象的例子，基础
先贴Tarjan的板子：
vector<int> G[MAXN];
int n;
int dfn[MAXN], low[MAXN];
bool ins[MAXN], vis[MAXN];
int sta[MAXN], top;
vector<int> scc[MAXN];
int cnt;
int bel[MAXN];//每个点属于哪个
void dfs(int u) {
dfn[u] = low[u] = ++dfn[0];
vis[u] = 1;
sta[++top] = u;
ins[u] = 1;
for (int v : G[u]) {
if (!vis[v])
dfs(v), low[u] = min(low[u], low[v]);
else if (ins[v])
low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
cnt++;
while (sta[top] != u) {
int v = sta[top--];
ins[v] = 0;
scc[cnt].push_back(v);
bel[v] = cnt;
}
int v = sta[top--];
ins[v] = 0;
scc[cnt].push_back(v);
bel[v] = cnt;
}
}
Tarjan算法求强连通分量的两种写法
上面是第一种写法。大部分时间都用的这一种，因为它和求双连通分量的Tarjan差不多。
很少看到对第两种写法的具体说明，在这里做简单的补充。
第一种写法的中间部分可以改为：
for (int v : G[u]) {
if (!vis[v])
dfs(v), low[u] = min(low[u], low[v]);
else if (ins[v])
low[u] = min(low[u], low[v]);
}
区别在于：对 栈中的节点 \(v\) 的更新方式.
产生区别的原因是：
第一种写法中的
low[u]表示 \(u\) 所在子树中的节点经过至多一条非树边能到达的节点中最小的dfs序。第二种写法中的
low[u]表示表示 \(u\) 所在子树中的节点能到达的节点中最小的dfs序。这是更好理解的做法。
两种写法是等价的
如上图 (假设点的编号就是该点的DFN序)
在第一中写法中,low[6]=4，low[4]=2
在第二中写法中,low[6]=low[4]=2
可以肯定的是，第二种写法是对的，但是第一种为什么也是对的呢？因为low[u]最终只要小于dfn[u]就不会认定这个点为强连通分量的根。我们只需要保证找到的“根”是对的，强连通分量就是对的，所以只用保证low[u]<dfn[u]就可以了，我们不关心low[u]的具体值。
具体运用
常见的使用场景是：
对一张存在环的有向图求出强连通分量，缩点，即将原图转化为DAG。
缩点的过程：求出每个点属于的强连通分量编号，原图中的边更新到新图上，注意判重边（map）。
习题：
P2272 [ZJOI2007] 最大半连通子图：典型缩点题目
网络协议：有一个性质补充，使一张图变为强连通的需要添加的最少边数为：这张图缩点后的DAG中，入度为0的点数量与出度为0的点的数量的最大值