强连通分量就像一个“终极死党群”群里的任何一个人都能通过私聊或群聊直接或间接地联系到群里的其他任何人而且群里所有人对外界的联系都是单向的外人进不来里面也不会有人去主动联系圈外人。在图里这就是一个最大的子图里面任意两点互相可达。【核心思想】要找出有向图里所有的“死党群”主要有两种方法Tarjan 算法想象你拿着一个计时器遍历图。每走进一个节点就打个时间戳记录下“我能回溯到的最早节点”low 值。如果走着走着发现一个节点的所有后代都找不到比它自己更早的节点了那它就是这个“死党群”的根。我们用栈来暂存成员找到根后就把栈里对应的成员全弹出打包成一个强连通分量。Kosaraju 算法这个思路很巧妙利用了“反图”。你正常走一遍正图按离开时间的倒序排个队。然后穿越到镜面世界反图按照刚才的倒序再走一遍。每一次 DFS 能到达的节点就是一个强连通分量。它很好地体现了“顺着走和逆着走都能到”的互补思维。【算法可视化】假设有一个有向图关系如下0 喜欢 11 喜欢 22 喜欢 0 0,1,2 围成一个圈2 喜欢 33 喜欢 44 喜欢 3 3,4 是另一个小圈子Tarjan 算法的发现过程文字模拟从 0 开始DFS0时间1 - 1时间2 - 2时间3 - 3时间4。到 3 后发现它能走到 4时间5。4 没有别的孩子了但 4 指向 3而 3 还在栈里所以 4 的 low 值更新为 3 的时间戳。4 的 low 值 自己的时间戳它不是根。回溯到 33 发现通过 4 能回到自己它的 low 值也和 4 一样了。此时dfn[3] low[3]不low[3]已经被更新不等于了。最后当回溯到dfn low的那个节点时比如从 2 走到了 00 的时间戳是最早的它的 low 值等于自己的时间戳。那么此时栈里从栈顶到 0 之间的所有节点都打包带走这就是第一个 SCC{0,1,2}。继续清理发现 3 还没访问完继续 DFS 得到 {3,4}。【代码模板】C 实现 Tarjan关键行已注释#include vector #include stack using namespace std; const int MAXN 10005; vectorint graph[MAXN]; int dfn[MAXN], low[MAXN], scc_id[MAXN], timer 0, scc_cnt 0; stackint st; bool in_stack[MAXN]; void tarjan(int u) { dfn[u] low[u] timer; // 打上时间戳 st.push(u); in_stack[u] true; for (int v : graph[u]) { if (!dfn[v]) { tarjan(v); // 我的孩子能回溯到更早我也能 low[u] min(low[u], low[v]); } else if (in_stack[v]) { // v 是我在栈里的祖先我可以通过它回到更早 low[u] min(low[u], dfn[v]); } } // 如果我的 dfn low我就是这个 SCC 的根 if (dfn[u] low[u]) { scc_cnt; int cur; do { cur st.top(); st.pop(); in_stack[cur] false; scc_id[cur] scc_cnt; // 给这个节点分配 SCC 编号 } while (cur ! u); } }【经典例题】模板题求 SCC 个数洛谷 P2863 [USACO06JAN] The Cow Prom S题意统计有向图中大小大于 1 的强连通分量数量。思路直接跑 Tarjan。在打包时统计每个 SCC 的大小最后数一下有几个大于 1 的 SCC 就行。核心代码片段int ans 0; for (int i 1; i n; i) if (!dfn[i]) tarjan(i); vectorint scc_size(scc_cnt 1, 0); for (int i 1; i n; i) scc_size[scc_id[i]]; for (int i 1; i scc_cnt; i) if (scc_size[i] 1) ans; cout ans endl;缩点后 DP洛谷 P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G题意每头牛都希望被所有牛欢迎。A 喜欢 BB 喜欢 C那么 A 也喜欢 C。问有多少头牛被所有牛喜欢。思路先缩点。缩完后得到一个 DAG。如果 DAG 里唯一一个出度为 0 的强连通分量那么它里面的所有牛都是明星。因为别的点最终都能走到它。如果存在多个出度为 0 的分量答案就是 0。核心代码片段// 缩点后重新建图统计出度 vectorint out_deg(scc_cnt 1, 0); for (int u 1; u n; u) { for (int v : graph[u]) { if (scc_id[u] ! scc_id[v]) { out_deg[scc_id[u]]; // 不是完全相同分量内的边就是外部出度 } } } int zero_out 0, ans_scc_id 0; for (int i 1; i scc_cnt; i) { if (out_deg[i] 0) { zero_out; ans_scc_id i; } } if (zero_out 1) { int ans 0; for (int i 1; i n; i) if (scc_id[i] ans_scc_id) ans; cout ans; } else cout 0;【复杂度与对比】算法时间复杂度空间复杂度优点缺点TarjanO(V E)O(V)一次 DFS 就搞定常数更小代码更简短理解起来稍微绕一点KosarajuO(V E)O(V E)思路简单清晰“正反图”逻辑直观非常适合讲解需要存反图要跑两遍 DFS实际中常数稍大一般竞赛里直接背 Tarjan 模板就行高效实用。【举一反三】缩点之后有向图变成了有向无环图DAG很多难题瞬间变得清爽拓扑排序 DP在 DAG 上可以轻松求最长路、最短路径、路径计数。必经点/必经边问题在 DAG 上求支配树比一般图简单得多。2-SAT 问题判断一组合选命题是否成立核心就是把逻辑推导图缩点看一个变量和它的反状态是否在同一个 SCC 里。掌握 SCC其实就是掌握了把复杂有向图“层级化”的第一步是进阶图论题目的敲门砖。