【模板】Tarjan求强连通分量

有人说这篇博客不是很友好，所以我加了点解释，感觉是不是友好多了？

dfn[u]表示节点u在dfs时被访问的次序。

low[u]表示节点u能够追溯到的最远的祖先的dfn。

ins[u]表示节点u是否在栈中。

belong[u]表示节点u所属的SCC标号，也可以说可以缩成的点的标号。

若u的子节点v可以追溯到节点x(x可能为u的祖先)，那么u也可以追溯到节点x。

同时如果是最远祖先那么祖先在dfs中的顺序肯定最小，所以取min值。

如果搜索到的点已经在栈中了，那么当前点的祖先肯定可以是在栈中的点。

1 #include <cstdio> 2 #include <cstring> 3 #include <stack> 4 5 int n, m, cnt, index, ans, size; 6 int head[10001], to[10001], next[10001], dfn[10001], low[10001], belong[10001]; 7 bool ins[10001]; 8 std::stack <int> s; 9 10 inline void add(int x, int y) 11 16 17 void tarjan(int u) 18 31 else if(ins[v]) low[u] = std::min(low[u], dfn[v]); 32 } 33 if(low[u] == dfn[u]) 34 while(v != u); 43 } 44 } 45 46 int main() 47 56 for(i = 1; i <= n; i++)//有可能是非连通图 57 if(!dfn[i]) 58 tarjan(i); 59 printf("%d\n", size); 60 for(i = 1; i <= n; i++) printf("%d ", belong[i]); 61 return 0; 62 }
View Code

上一篇：【模板】Dijkstra的heap优化

下一篇：doris单机安装部署

---

模板 tarjan SCC