// Tarjan算法求有向圖強(qiáng)連通分量并縮點(diǎn) /*強(qiáng)連通縮點(diǎn)與雙連通縮點(diǎn)大同小異，也就是說將強(qiáng)連通分支縮成一個點(diǎn)之后，沒有強(qiáng)連通，成為有向無環(huán)圖，在對圖進(jìn)行題目的操作。*/ #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #include<vector> #include<queue> using namespace std; const int N = 100010, M = 1000010; int ver[M], Next[M], head[N], dfn[N], low[N]; int stack[N], ins[N], c[N]; int vc[M], nc[M], hc[N], tc; vector<int> scc[N]; int n, m, tot, num, top, cnt;void add(int x, int y) {ver[++tot] = y, Next[tot] = head[x], head[x] = tot; }void add_c(int x, int y) {vc[++tc] = y, nc[tc] = hc[x], hc[x] = tc; }void tarjan(int x) {dfn[x] = low[x] = ++num;stack[++top] = x, ins[x] = 1;for (int i = head[x]; i; i = Next[i])if (!dfn[ver[i]]) {tarjan(ver[i]);low[x] = min(low[x], low[ver[i]]);}else if (ins[ver[i]])low[x] = min(low[x], dfn[ver[i]]);if (dfn[x] == low[x]) {cnt++; int y;do {y = stack[top--], ins[y] = 0;c[y] = cnt, scc[cnt].push_back(y);} while (x != y);} }int main() {cin >> n >> m;for (int i = 1; i <= m; i++) {int x, y;scanf("%d%d", &x, &y);add(x, y);}for (int i = 1; i <= n; i++)if (!dfn[i]) tarjan(i);for (int x = 1; x <= n; x++)for (int i = head[x]; i; i = Next[i]) {int y = ver[i];if (c[x] == c[y]) continue;add_c(c[x], c[y]);} }

?

?

總結(jié)

以上是生活随笔為你收集整理的图论--SCC缩点--Tarjan的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。