強連通分量

• 圖中找到一個最大的子圖，使得子圖中任意兩個節點相互到達。
• 一個點也是一個強連通分量

Tarjan

構成強連通分量是必定是dfs樹的一棵子樹，在對樹進行dfs的時候記錄訪問時間dfn和以該節點為根節點的子樹的最小編號low，將節點加入棧中并遞歸它的子節點，子節點在棧中更新根節點的low，子節點沒有訪問過就繼續遞歸下去。
在回溯的時候，當dfn == low 表示該點可以通過棧中的節點回到原點，也就形成一個強連通分量

int dfn[maxn], low[maxn], Stack[maxn], inStack[maxn], belong[maxn], in[maxn], ts, cnt, len; void init(int n) {for (int i = 1; i <= n; ++i) g[i].clear();ts = cnt = len = 0;fill(dfn, dfn+n+1, 0);fill(inStack, inStack+n+1, 0); } void tarjan(int u) {dfn[u] = low[u] = ++ts;inStack[u] = 1;Stack[len++] = u;for (int i = 0; i < (int)g[u].size(); ++i) {int v = g[u][i];if (!dfn[v]) {tarjan(v);low[u] = min(low[u], low[v]);}else if (inStack[v]) low[u] = min(low[u], dfn[v]);}if (dfn[u] == low[u]) {cnt++;while (1) {int top = Stack[--len];belong[top] = cnt;inStack[top] = 0;if (top == u) break;}} } for (int i = 1; i <= n; ++i) {if (dfn[i]) continue;tarjan(i); }

總結

以上是生活随笔為你收集整理的Tarjan 强连通分量的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。