题源：https://www.luogu.com.cn/problem/P2341
又是一道debug了几个小时的题。。不看测试数据根本发现不了bug。。
1.首先是tarjan算法要设置多个起点，有可能一个起点出发不能遍历到所有点。
2.入度是对于一个节点儿子而言的，并不包含它儿子的儿子。。所以我一开始判断入度的个数是否等于总连通分量个数的方法是错误的。（通过可视化方法，画一个拓扑排序图，或是举反例（也是画图）验证算法是否错误）
3.还可能存在几个完全独立的连通分量（包含两个或两个以上，所以仅判断所给数据是否覆盖了所有n是不充分的）。例外的情况还是要再判断一次，万一出错了呢。。遵循尽量排除非法情况原则。
另外还有一个小疑问：访问到已存在于栈中的节点时low[u] = min(low[u], dfn[v]) 中的dfn可否改为low？（就可以少开一个数组了）
参考这篇博客: https://blog.csdn.net/elijahqi/article/details/80614953 求割点时可能会影响，连通分量应该是不影响的
贴一个自己巨丑的代码：
#include <iostream> #include <stdio.h> #include <cstring> #include <set> //#define LOCAL using namespace std; set<int> scc1[10005]; //与后面scc2一起双向存储强连通分量 int dfn[10005], low[10005], tms = 0, stak[10005], tp = -1, v[10005], sz[10005], vc = 0; struct Edge { int next, to; } edge1[50005]; int head1[10005], scc2[10005], sccnt = 0, e1 = 0, deg[10005]; void tarjan(int u) { #ifdef LOCAL // cout << tms << " : " << u << endl; #endif low[u] = dfn[u] = ++tms, stak[++tp] = u; for (int i = head1[u]; i; i = edge1[i].next) { int v = edge1[i].to; if (!dfn[v]) tarjan(v), low[u] = min(low[v], low[u]); else if (!scc2[v]) low[u] = min(low[u], dfn[v]); // ?? dfn[v] <=> low[u] } if (dfn[u] == low[u]) { ++sccnt; while (stak[tp] != u) { scc2[stak[tp]] = sccnt, scc1[sccnt].insert(stak[tp]), --tp, sz[sccnt]++; } scc2[stak[tp]] = sccnt, scc1[sccnt].insert(stak[tp]), --tp, sz[sccnt]++; //u也要取出 } } void rebuild() { int w, cnt; for (int i = 1; i <= sccnt; ++i) { cnt = 0; memset(v, 0, sizeof(v)); // 防止重复加出度，不过没什么用了。。如果只判断是否为0的话加一个出度就可以退出了。。 v[i] = 1; for (int j : scc1[i]) { for (int t = head1[j]; t && cnt < sccnt; t = edge1[t].next) { #ifdef LOCAL cout << i << " : " << j << " : " << cnt << endl; #endif w = scc2[edge1[t].to]; if (!v[w]) v[w] = 1, deg[i]++, cnt++; } } } } int main() { #ifdef LOCAL freopen("popular9.in", "r", stdin); freopen("out.txt", "w", stdout); #endif int n, m, x, y; scanf("%d%d", &n, &m); memset(dfn, 0, sizeof(dfn)); memset(low, 0, sizeof(low)); memset(head1, 0, sizeof(head1)); memset(scc2, 0, sizeof(scc2)); memset(v, 0, sizeof(v)); memset(deg, 0, sizeof(deg)); memset(sz, 0, sizeof(sz)); for (int i = 0; i < m; ++i) { scanf("%d%d", &x, &y); if (!v[x]) v[x] = 1, vc++; if (!v[y]) v[y] = 1, vc++; //是否枚举到所有n（简单优化？） edge1[++e1].next = head1[x], edge1[e1].to = y, head1[x] = e1; } if (vc < n) { cout << 0; return 0; } for (int i = 1; i <= n; ++i) { if (!dfn[i]) //tarjan算法要循环一遍。。有可能中途栈就弾完了 { #ifdef LOCAL // cout << i << endl; #endif tarjan(i); //多个起点 } } rebuild(); #ifdef LOCAL for (int i = 1; i <= sccnt; ++i) cout << i << " : " << sz[i] << endl; #endif #ifdef LOCAL cout << "sccnt : " << sccnt << endl; #endif int mn = 0; bool f = false; for (int i = 1; i <= sccnt; ++i) { #ifdef LOCAL cout << deg[i] << endl; #endif if (deg[i] == 0) { if (mn == 0) mn = i; else { f = true; break; } } } if (f) cout << 0; else cout << sz[mn]; }
原文：https://www.cnblogs.com/jionkitten/p/12213242.html