强连通分量(Tarjan算法)
-
前言
第一件事：没事不要while(m–)，会带来不幸
第二件事：看博客先看看评论，如果博主他写错了的话… -
简介
先讲几个定义
-
强连通：两个顶点 u u u， v v v 可以相互到达
-
强连通图：图中的任意两个顶点可以相互到达(就是图中有一块边缠在一起)
-
强连通分量(scc)：图 G G G 不是一个强连通图，但其子图 G ′ G^\prime G′ 是 G G G 的最大强连通子图，则称 G ′ G^\prime G′ 为一个强连通分量
tarjan算法就是一个可以找出图中所有强连通分量的方法。
-
-
原理
维护两个数组：
dfn[] : 时间戳。深搜这个图，dfn[i] 表示 第 i 个点是什么时候被搜到的
low[] : 深搜的这个图里正常的话肯定有环，low[i] 就表示第 i 个点属于哪个时间戳节点的环里
(表达很抽象自己悟233，或者看后面图解过程)
同时手打一个栈，把搜过的点压进栈
如图，从点1开始深搜，给搜过的点打上时间戳dfn，初始化low，stack = 1 3 2
当搜到点2时，下一个搜到了1，1已经被搜过了(已经被搜过了看 dfn[] != 0 )，且1在栈内
修改 low[2] = min(low[2], dfn[1]); (注意绕回根节点的时候是将该点的low和根节点的dfn比较)
此时点2搜完了，回溯到点3. 点3是回溯来的修改low肯定是和点2的low比较
即修改 low[3] = min(low[2], low[3]);
点3继续深搜，给4,5打上时间戳，同时入栈4,5，此时栈内有 stack = 1 3 2 4 5
5继续搜，搜到4，点4已经搜过且在栈内，修改low[5] = min(low[5], dfn[4])
回溯到点4，点4修改low[4] = min(low[4], low[5])
下一步是关键，此时点4已经搜完，即将退出回溯到点3，而我们发现点4的dfn[4] == low[4]
也就是说点4就是一块强连通分量的节点！
此时开始出栈，直到点4出栈为止。即剩下的stack = 1 3 2
我们给出栈的点全部打上scc标记，即
待出栈结束，回溯到点3
点3此时修改low[3] = min(low[3], low[4]), 显然low3不变
继续回溯到点1，发现点1已经搜完，且dfn[1] == low[1]
同上述点4，出栈打标记
此时栈已经空了，从1开始深搜已经结束，但很明显还有一个6没有被搜过
可以很明显看出上述算法不一定能走遍整个图，所以需要以每一个点为起点深搜一次，判断标准是是否被搜过(即dfn[] != 0)
for(int i = 1; i <= n; i++){
if(!dfn[i]) tarjan(i);
}
在坚持一下，马上就要结束了
此时其实还有最后问题没有解决，就是那个栈有什么用，让我们继续深搜点6
dfn[6] = 6, low[6] = 6，下一个要搜的点是2
2已经被搜过，但是和上面都不一样的地方来了！2此时不在栈里
所以我们不用更新low[6]，直接结束搜点6.
最后，low[6] == dfn[6]， 打上scc标记，整个算法就讲完了。
-
代码
用链式前状星存图，手打栈(当然stl也可以)
void tarjan(int x) { sta[++top] = x; //手打入栈 instack[x] = 1; dfn[x] = low[x] = ++cnt; //初始化dfn和low //核心代码，深搜这个点 for (int i = head[x]; i; i = edge[i].next) { int to = edge[i].to; if(!dfn[to]){ //如果下一个点没有被搜过， tarjan(to); //继续深搜 low[x] = min(low[x], low[to]); //更新low } else if(instack[to]){ //如果下一个点已经被搜过，看他在不在栈里 low[x] = min(low[x], dfn[to]); //更新low } } //如果dfn==low，即找完了一整块强连通分量，出栈+标记 if(dfn[x] == low[x]){ tot++;//计数器++，第几个强连通分量 while(sta[top+1]!=x){ //不加1的话x这个点不会被出栈 scc[sta[top]] = tot; //打标记 instack[sta[top--]] = 0;//出栈 } } } -
例题：P3387 【模板】缩点
#define _CRT_SECURE_NO_WARNINGS #include <bits/stdc++.h> using namespace std; #define ll long long const int N = 1e4 + 5; const int M = 1e5 + 5; int read() { int x = 0, f = 1; char ch = getchar(); while (ch < '0' || ch>'9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar(); } return x * f; } /// struct Edge { int to; int from; int next; }edge[M], edge2[M]; int head[N], head2[N]; int cnt; void add_edge(int u, int v) { edge[++cnt].to = v; edge[cnt].from = u; edge[cnt].next = head[u]; head[u] = cnt; } void add_edge2(int u, int v) { edge2[++cnt].to = v; edge2[cnt].from = u; edge2[cnt].next = head2[u]; head2[u] = cnt; } int w[N]; int low[N]; int dfn[N]; int scc[N]; int sum[N]; int tot;//计数有几个强连通分量 //手打栈 bool instack[N]; int sta[N]; int top; void tarjan(int x) { sta[++top] = x; instack[x] = 1; dfn[x] = low[x] = ++cnt; for (int i = head[x]; i; i = edge[i].next) { int to = edge[i].to; if(!dfn[to]){ tarjan(to); low[x] = min(low[x], low[to]); } else if(instack[to]){ low[x] = min(low[x], dfn[to]); } } if(dfn[x] == low[x]){ tot++; while(sta[top+1]!=x){ scc[sta[top]] = tot; sum[tot] += w[sta[top]]; instack[sta[top--]] = 0; } } } int dp[N]; void dfs(int x) { if (dp[x]) return; dp[x] = sum[x]; int sum = 0; for (int i = head2[x]; i; i = edge2[i].next) { int to = edge2[i].to; if (!dp[to]) dfs(to); sum = max(sum, dp[to]); } dp[x] += sum; } int main() { int n, m; scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) { w[i] = read(); } for(int i = 0; i < m; i++){ int a = read(); int b = read(); add_edge(a, b); } cnt = 0;//偷懒给tarjan复用 for (int i = 1; i <= n; i++) { if (!dfn[i]) tarjan(i); } //建新的图edge2，新图是DAG有向无环图 cnt = 0;//偷懒x2 for (int i = 1; i <= m; i++) { int u = edge[i].from; int v = edge[i].to; if(scc[u] != scc[v]) add_edge2(scc[u], scc[v]); } //深搜这个edge2 int ans = 0; for (int i = 1; i <= tot; i++) { if (!dp[i]) { dfs(i); ans = max(ans, dp[i]); } } printf("%d\n", ans); system("pause"); return 0; } -
尾声
感觉这个应该是最详细的tarjan博客了23333
最后提醒两点：看博客注意看评论会有大牛指出错误，不要对着错博客研究半天怎么都写不对2333
第二个，上面的代码94行画图的时候，老老实实for(int i = 0;i < m; i++)，别嫌那么一点点麻烦来个while(m--)，108行第二次画图的时候就啥都没干了