强连通分量、割点与割边 | 王心俊老师信息学奥赛课件

板块	核心内容	对应大纲
dfn 与 low	一次 DFS 打两个时间戳，O(n+m)	强连通分量【7】
有向图 SCC	low[u]==dfn[u] 出栈成分量	强连通分量【7】
缩点 + DAG DP	压点后图变 DAG，按拓扑序 DP	强连通分量【7】
无向图割点	low[v]≥dfn[u]；根节点需 ≥2 个孩子	割点、割边【7】
无向图割边	low[v]>dfn[u]；重边用边编号处理	割点、割边【7】
点双 / 边双	点双由边栈划分，边双删桥后连通块	割点、割边【7】

模块 02

知识探究

先啃透 dfn 与 low 这两个变量的含义，再把 Tarjan 分别套到有向图与无向图上，最后用三道真题代码把模板焊死。

1dfn 与 low：Tarjan 的两块基石核心

Tarjan 算法的全部力量来自两个数组。理解它们，等于理解了整讲内容的一半。

🕐

dfn[u]

u 被 DFS 第一次访问到的序号，全局计数器 ++tim 得到，唯一且不可变

↩️

low[u]

u 子树内能「回头够到」的最小 dfn，初值 = dfn[u]

🔄

回溯合并

儿子走完回来，用 low[v] 更新 low[u]：low[u]=min(low[u],low[v])

📐 更新规则拆解（有向图版本）

设当前在 u，枚举它的出边 u→v：

情况①：v 从未访问过（dfn[v]==0）。则 u→v 是树边。递归进入 v，返回后执行
low[u] = min(low[u], low[v]); —— 儿子能绕到多早，父亲跟着沾光。

情况②：v 已访问，且 v 还在栈中（ins[v]==true）。说明 v 是本轮尚未结算的「同伴」，边 u→v 是一条回边/横叉边，于是
low[u] = min(low[u], dfn[v]); —— 注意这里用的是 dfn[v] 而不是 low[v]。

情况③：v 已访问，但 v 已经出栈（ins[v]==false）。说明 v 属于另一个已经结算完的 SCC，这条边对 low 毫无贡献，直接跳过。

为什么情况②必须用 dfn[v]？因为 low[v] 描述的是「v 能到多早」，可能是 v 自己绕到了更早的地方；但从 u 直接走到 v，只能「站到 v 的位置」，不能借用 v 的视野。用 low[v] 会把不该合并的分量黏在一起。

✅ 正确写法

else if (ins[v]) low[u] = min(low[u], dfn[v]);

只对「栈内节点」用 dfn[v] 更新。

❌ 常见错误

else low[u] = min(low[u], dfn[v]);

漏掉 ins 判断，指向已结算分量的边也会缩小 low，导致 SCC 被错误合并、数量偏少。

▶ Tarjan 递归全过程：dfn/low 更新与出栈成 SCC

1从 1 号点进入 tarjan(1)：dfn[1]=low[1]=1，1 入栈。栈 = [1]

2走树边 1→2：dfn[2]=low[2]=2，2 入栈。栈 = [1,2]

3走树边 2→3：dfn[3]=low[3]=3，3 入栈。栈 = [1,2,3]

43 有一条回边 3→1，而 1 仍在栈中 → low[3] = min(3, dfn[1]=1) = 1。3 够到了最早的祖先！

53 递归返回 2：low[2] = min(2, low[3]=1) = 1

62 递归返回 1：low[1] = min(1, low[2]=1) = 1

7检查 1：low[1]==dfn[1] → 1 是分量根，不断弹栈直到弹出 1 → 得到 SCC#1 = {3,2,1}，同时把这些点的 ins 清零

8继续找未访问点，从 4 进入：dfn[4]=low[4]=4，4 入栈。栈 = [4]

9走树边 4→5：dfn[5]=low[5]=5，5 入栈。栈 = [4,5]

105 有回边 5→4，4 在栈中 → low[5] = min(5, dfn[4]=4) = 4；返回 4 后 low[4] = min(4, low[5]=4) = 4

11low[4]==dfn[4] → 弹栈得到 SCC#2 = {5,4}。全图共 2 个强连通分量，缩点后剩 1 条边：SCC#1 → SCC#2

提示：点击「自动演示」按顺序高亮每一步，观察 low 值如何一路向上传播，以及「谁先出栈」决定了 SCC 的编号顺序。

变量	含义	初始值	更新方式
dfn[u]	u 的 DFS 进入时间戳	0（未访问）	++tim，只赋值一次
low[u]	u 子树可达的最小 dfn	dfn[u]	min(low[u], low[v]) 或 min(low[u], dfn[v])
ins[u]	u 是否在 Tarjan 栈中	false	入栈置 1，出栈置 0
stk[] / top	待结算节点栈	空	进入时压栈，low[u]==dfn[u] 时弹栈
id[u] / cnt	u 所属 SCC 编号 / 总数	0	弹栈时统一赋同一个 id

2强连通分量与缩点高频

Tarjan 在 low[u]==dfn[u] 时弹出栈中「u 及其之后的所有节点」，它们恰好构成一个 SCC。这一步之所以正确，是因为：

🧠 正确性直觉（理解即可，不必背证明）

① 若 low[u]==dfn[u]，说明 u 的子树里没有一个点能绕到 u 的祖先，因此 u 是这坨节点的「最高入口」。

② 栈中 u 之上的点，都是 u 的子树里尚未结算的点；它们都能到达 u（否则早就被弹掉了），而 u 也能沿 DFS 树到达它们。

③ 因此栈顶到 u 这一段的所有点两两可达，构成一个极大强连通点集，并且就是我们要的 SCC。

④ 出栈后这些点再也不参与后续计算，天然满足「每个点只属于一个 SCC」。

缩点：把强连通块「捏」成一个点必掌握

对原图跑一遍 Tarjan，得到每个点的 id[u]（属于哪个 SCC）与每个 SCC 的 sz[c]（大小）。
遍历原图所有边 u→v，若 id[u] != id[v]，就在新图上连一条 id[u] → id[v]。
新图一定无环——若还有环，环上的点本来就在同一个 SCC 里。
把「点权」汇聚到 SCC 上：w[id[u]] += a[u]，之后就能在 DAG 上做最短路、最长路、计数、博弈等 DP。

复杂度：Tarjan O(n+m) + 重构图 O(n+m) = O(n+m)，非常划算。

🔑 缩点三连

先跑 Tarjan 打 id → 再扫边建新图 → 最后在新图（DAG）上做 DP。
看到「有环的有向图 + 路径统计」，第一反应就是缩点。

3无向图的割点判定核心

在无向连通图上做 DFS，得到的是一棵DFS 树，且不存在横叉边（无向图中所有非树边都是连接祖先与后代的回边）。这让判断变得干净利落。

📐 割点判定规则

情况①（非根节点 u）：若存在儿子 v 使得

low[v] >= dfn[u]

则 u 是割点。含义：v 的子树没有任何一条回边能绕过 u 往上走，所以删掉 u 之后 v 的子树就和上面断开了。

情况②（根节点 rt）：根节点的 low 判断会失效（它没有祖先）。改用孩子数量：

若 root 的儿子数 >= 2，则 root 是割点

含义：根的两个儿子之间在 DFS 树中不可能有边相连（否则第二个儿子会从第一个儿子那里被访问到），所以删掉根后它们必然分家。

为什么割点是 ≥，割边是 > ？因为删点会连 u 本身一起删掉，而删边不删端点，两者差的就是 u 这一个端点。

STEP 1进入 u 打时间戳

STEP 2枚举邻边

STEP 3递归子树并回传 low

STEP 4回边更新 low

STEP 5结算割点标记

对比项	有向图 SCC	无向图割点
非树边更新 low	仅当 v 在栈中：min(low[u], dfn[v])	只要 v 已访问：min(low[u], dfn[v])
是否用栈	需要，用于划分分量	不需要
结算条件	low[u] == dfn[u] → 出栈成 SCC	low[v] ≥ dfn[u] → u 是割点
根节点特殊处理	无	有：根看孩子数是否 ≥ 2
复杂度	O(n+m)	O(n+m)

4无向图的割边判定与重边处理易错

割边（桥）判定只比割点严格一点点：把 >= 改成 >。

📐 割边判定规则

对 DFS 树上的树边 u→v，若

low[v] > dfn[u]

则边 (u,v) 是割边。含义：v 的子树里连一条回到 u 或其祖先的回边都没有——注意连回到 u 自身都不行，因为如果是回边到 u，删掉边 (u,v) 后 v 依然能通过这条回边到达 u，连通性不下降。

⚠️ 重边的陷阱：如果 u 和 v 之间有两条边，那任何一条都不是割边——删掉一条还有另一条。但普通的「记录父亲节点、跳过父亲」写法会把第二条边当成回到父亲的边而误判，因此必须用边编号（成对存边）识别反向边。

成对存边技巧：链式前向星中，边从下标 2 开始编号，则第 i 条边与第 i^1 条边互为反向边（2↔3、4↔5……）。DFS 时传入「进入 u 的那条边的编号 ein」，遇到 i == (ein^1) 就跳过——只跳过那一条反向边，其余重边照样参与 low 更新，问题迎刃而解。

❌ 用父节点判重（会被重边坑）

if (v == fa) continue;

有重边时，第二条边也是「到 fa 的边」，却被当成树边的反向边跳过了，导致 low[v] 无法变小，假割边出炉。

✅ 用边的编号判重（推荐）

if (i == (ein ^ 1)) continue;

只跳过唯一那条反向边，重边全部保留参与 low 更新，割边判定正确。

▶ 割边判定全程演示：图 1-2、2-3、2-4、3-5、4-5、5-6

1从 1 出发：dfn[1]=low[1]=1。树边 1→2：dfn[2]=low[2]=2

2树边 2→3：dfn[3]=low[3]=3；树边 3→5：dfn[5]=4

3树边 5→4：dfn[4]=5；4 有回边到 2 → low[4]=min(5, dfn[2]=2)=2，回传得 low[5]=2、low[3]=2（环 2-3-5-4 内没有桥）

4树边 5→6：dfn[6]=low[6]=6，6 没有其他出边

5判定 5→6：low[6]=6 > dfn[5]=4 → 5-6 是割边！（6 的子树没有任何回边，删边后 6 被孤立）

6回到 2：4→2 的回边让 low[2]=2 不变；判定树边 2→3：low[3]=2 不大于 dfn[2]=2 → 非割边

7回到 1：判定树边 1→2：low[2]=2 > dfn[1]=1 → 1-2 是割边！（点 1 只靠它和其余部分相连）

8结论：割边共 2 条 —— {1,2} 与 {5,6}，与「炸铁路」样例答案完全一致

观察：环 2-3-5-4 上每条树边都因 low[v] ≤ dfn[u] 而「幸免」——环内的边永远不可能是桥。

C++割边 Tarjan 核心（成对存边）

void add(int u, int v) { e[++tot] = {v, head[u]}; head[u] = tot; }   // tot 从 1 开始
void add2(int u, int v) { add(u, v); add(v, u); }           // 成对添加：2/3、4/5 ...

void tarjan(int u, int ein) {           // ein = 进入 u 的那条边的编号
    dfn[u] = low[u] = ++tim;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (i == (ein ^ 1)) continue;     // 只跳过那一条反向边
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])           // 严格大于 → 割边
                isBridge[i] = isBridge[i ^ 1] = 1;
        } else low[u] = min(low[u], dfn[v]);
    }
}

5点双连通分量与边双连通分量进阶

割点和割边分别催生出两种「分解」方式，它们把图切成整齐的小块。

🧩 边双连通分量 (e-BCC)

定义：删掉所有割边后剩下的每个连通块（注意不是「没有割边的图」，而是「删桥后的连通块」）
求法：先 Tarjan 标记所有割边，再对不含割边的子图做一次 DFS/BFS 染色
性质：任一 e-BCC 中任意两点之间至少有 2 条边不相交的路径（边双连通 ⟺ 无割边）
缩点后：一个 e-BCC 缩成一点，剩下的边全是割边，新图必定是一棵树

🧩 点双连通分量 (v-BCC)

定义：不含割点的极大子图，必须至少包含 2 个点、1 条边（孤立点单独算一个）
求法：Tarjan 中维护一个边栈，遇到 low[v] ≥ dfn[u] 就弹边直到 (u,v)，弹出的边与 u 构成一个 v-BCC
性质：一个割点可以同时属于多个点双（这是点双最容易混淆的地方）
应用：圆方树的基础，用来处理「必经点」「点权路径」类问题

对比项	点双连通分量	边双连通分量
删什么会坏	删点	删边
分量是点的划分吗	不是，割点属于多个分量	是，边双是点集的严格划分
分量内元素	点集 + 边集	点集
典型求法	Tarjan + 边栈	Tarjan 标桥 + 染色
缩点后结构	圆方树（树）	一棵树（点 = 边双）

▶ 点双弹边栈演示：三角形 1-2-3 再挂一条边 3-4

1进入 1：dfn[1]=1，边栈为空（点双算法压的是边，不是点）

2树边 1→2：dfn[2]=2，边 1-2 入栈 → 边栈 [1-2]

3树边 2→3：dfn[3]=3，边 2-3 入栈 → 边栈 [1-2, 2-3]

4回边 3→1：1 已访问 → low[3]=min(3, dfn[1]=1)=1，边 3-1 也入栈 → 边栈 [1-2, 2-3, 3-1]

5回溯到 2：low[3]=1 不满足 ≥ dfn[2]=2 → 不弹栈，三角形暂时留在栈里

6树边 3→4：dfn[4]=4，边 3-4 入栈。4 无出边，low[4]=4

7回溯到 3：low[4]=4 ≥ dfn[3]=3 → 弹边栈直到弹出 3-4：弹出 {3-4}，与端点 3 一起构成点双 {3,4}

8回溯到 1：low[2]=1 ≥ dfn[1]=1 → 弹到 1-2：弹出 {3-1, 2-3, 1-2}，构成点双 {1,2,3}

9结论：共 2 个点双；割点 3 同时出现在 {1,2,3} 和 {3,4} 中——这正是「割点可属于多个点双」的直观展示

对比边双：本图的割边是 3-4，删掉后 {1,2,3} 与 {4} 两个边双各成一团——同一个 DFS 数据，两种分解方式。

🔑 辨析诀

点双看割点、边双看割边；割点可重复出现，边双各点只归一家。

案例案例1：P2863 牛的舞会 —— SCC 计数入门模板

题目：给定 n 个点 m 条边的有向图，求点数 ≥ 2 的强连通分量个数。（1 ≤ n ≤ 10⁴，1 ≤ m ≤ 5×10⁴）

🔍 详细分析过程

第1步：识别模型。「互相可达的点集」= 标准 SCC 计数，直接套 Tarjan 模板。

第2步：记录分量大小。出栈时把该分量的点数累加到 sz[cnt]。

第3步：统计答案。遍历所有分量，若 sz[i] >= 2 则答案 +1（单个点自成 SCC，不算「舞会」）。

第4步：复杂度。每个点进出栈一次、每条边被扫一次，O(n+m) ≈ 6×10⁴，轻松通过。

C++P2863 完整代码 —— Tarjan 求强连通分量

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005, MAXM = 50005;
int n, m, tot, head[MAXN];
struct Edge { int to, nxt; } e[MAXM];
void add(int u, int v) { e[++tot] = {v, head[u]}; head[u] = tot; }

int dfn[MAXN], low[MAXN], tim;      // 时间戳与追溯值
int stk[MAXN], top, ins[MAXN];       // 手写栈 + 在栈标记
int id[MAXN], sz[MAXN], cnt;         // 分量编号 / 大小 / 个数

void tarjan(int u) {
    dfn[u] = low[u] = ++tim;
    stk[++top] = u; ins[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dfn[v]) {                 // 树边：递归后回传 low
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (ins[v]) {           // 回边且 v 在栈中
            low[u] = min(low[u], dfn[v]);   // 注意用 dfn[v]！
        }
    }
    if (low[u] == dfn[u]) {           // u 是分量根
        ++cnt;
        int v;
        do {
            v = stk[top--]; ins[v] = 0;
            id[v] = cnt; sz[cnt]++;
        } while (v != u);                // 一直弹到 u 为止
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        add(u, v);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i);        // 图可能不连通，逐点出发
    int ans = 0;
    for (int i = 1; i <= cnt; i++)
        if (sz[i] >= 2) ans++;          // 只统计点数 >= 2 的分量
    cout << ans << "\n";
    return 0;
}

🔍 代码逐段解析 · P2863 Tarjan SCC 计数

1建图 add()：链式前向星，e[++tot] = {v, head[u]} 头插法，head[u] 存 u 的第一条边号。本题有向图，只 add 一次

2dfn/low/tim：进入 tarjan 时 dfn[u]=low[u]=++tim，时间戳只赋一次；low 初值就是自己的 dfn

3stk[++top]=u; ins[u]=1：入栈并打「在栈中」标记。ins 是判回边能否更新 low 的唯一依据，漏打标记整题报废

4if (!dfn[v]) 树边：递归后 low[u]=min(low[u],low[v])，儿子的「回跳能力」传给父亲

5else if (ins[v]) 回边：只对栈内节点用 dfn[v] 更新；v 已出栈则属于别的 SCC，必须跳过（本讲易错 1）

6if (low[u]==dfn[u])：u 是分量根，do-while 弹栈到 u 为止，弹出点共用编号 cnt 并累加 sz[cnt]

7main 外层循环：for(i=1..n) if(!dfn[i]) tarjan(i)——图不一定连通，每个未访问点都要当一次起点

8统计答案：遍历 cnt 个分量，sz[i]>=2 才计数。若改成 >=1 输出的就是 SCC 总数

9易错点：① ins[v] 写成 !ins[v] 或直接漏掉；② do-while 写成 while 先判后弹，首元素没弹出造成死循环

对应输入 5 4：tarjan(1) 展开到 4 再回到 1 时 low[1]==dfn[1]，弹出 {4,2,1}；随后 tarjan(3) 单独访问 3→5，弹出 {5}、{3}，故答案为 1。

运行结果（已用 g++ 实测验证）

输入: 5 4
      2 4
      3 5
      1 2
      4 1
输出: 1

说明: SCC = {1,2,4}、{3}、{5}。环 1→2→4→1 构成唯一的
      大小 >= 2 的分量；3→5 是单向边，{3,5} 并不强连通

💡 边界思考

如果把判定条件改成 sz[i] >= 1，答案就变成了「SCC 总数」——这是本题最常见的改动方向。

如果图的边数是 10⁶ 而点数只有 10⁴，本模板依然 O(n+m)，完全够用。

案例案例2：缩点 + DAG 最长路必考套路

题目（P3387 缩点）：给定 n 点 m 边有向图，每个点有点权 a[u]（可能为负）。求一条路径，使路径经过的点权之和最大。一条路径重复经过同一个点，点权只算一次。（n ≤ 10⁴，m ≤ 10⁵）

🔍 详细分析过程

第1步：为什么必须缩点？「点权只算一次」+「可以绕圈」= 环上的点必然全拿。把 SCC 缩成一点，点权 = 分量内点权之和，问题变成 DAG 上的最大权路径，有环的麻烦彻底消失。

第2步：Tarjan 打 id。顺便维护 val[id] += a[u]。

第3步：重构图。扫原图所有边，若 id[u] != id[v] 就把 id[u] → id[v] 加入新图 g2（允许重边，DP 不受影响）。

第4步：DAG 上 DP。设 dp[c] 表示以分量 c 结尾的最大路径权。Tarjan 的编号顺序恰好是逆拓扑序：若存在边 id[u]→id[v]，必有 id[u] > id[v]。因此按编号从大到小转移即可。

第5步：答案 = max(dp[1..cnt])。

复杂度：O(n+m)，10⁵ 级别稳稳通过。

C++缩点 + DAG 最长路完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005, MAXM = 100005;
int n, m, a[MAXN], tot, head[MAXN];
struct Edge { int to, nxt; } e[MAXM];
void add(int u, int v) { e[++tot] = {v, head[u]}; head[u] = tot; }
int eu[MAXM], ev[MAXM];                // 存下原边，方便重构图

int dfn[MAXN], low[MAXN], tim;
int stk[MAXN], top, ins[MAXN];
int id[MAXN], cnt;
long long val[MAXN], dp[MAXN];        // 缩点后的点权 / DP 值
vector<int> g2[MAXN];                     // 缩点后的新图

void tarjan(int u) {
    dfn[u] = low[u] = ++tim;
    stk[++top] = u; ins[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        ++cnt; int v;
        do {
            v = stk[top--]; ins[v] = 0;
            id[v] = cnt;
            val[cnt] += a[v];              // 点权合并到新点
        } while (v != u);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i];
        add(eu[i], ev[i]);
    }
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);

    // 重构图：跨分量的边成为 DAG 的边
    for (int i = 1; i <= m; i++)
        if (id[eu[i]] != id[ev[i]])
            g2[id[eu[i]]].push_back(id[ev[i]]);

    // Tarjan 编号是逆拓扑序：编号大的在前，故从大到小转移
    for (int i = 1; i <= cnt; i++) dp[i] = val[i];
    for (int u = cnt; u >= 1; u--)
        for (int v : g2[u])
            dp[v] = max(dp[v], dp[u] + val[v]);

    long long ans = 0;
    for (int i = 1; i <= cnt; i++) ans = max(ans, dp[i]);
    cout << ans << "\n";
    return 0;
}

🔍 代码逐段解析 · 缩点 + DAG 最长路

1eu[]/ev[] 存原边：缩点后要重扫每条原图边来建新图，所以读入时顺手把边存下来

2val[cnt] += a[v]：弹栈结算时把分量内每个点的权值累加到缩点后的新点 val[c] 上，「环上点全拿」由此实现

3重构图 g2：扫 m 条原边，id[u]!=id[v] 才连边。允许重边——DP 取 max 时重边无影响

4dp 初始化：dp[i]=val[i]——路径至少经过这个分量自己

5for(u=cnt; u>=1; u--)：Tarjan 编号是逆拓扑序（边 id[u]→id[v] 必有 id[u]>id[v]），从大到小转移保证 dp[u] 已是最终值

6转移 dp[v]=max(dp[v], dp[u]+val[v])：到达 v 必然把 v 整个分量收入囊中，所以加上 val[v] 而不是 val[u]

7取答案：max(dp[1..cnt])——起点任意，答案就是所有分量 dp 值的最大值

8易错点：① 循环写成递增（见下方思考框反例）；② 点权和用 long long 防溢出；③ 重构图漏存 eu/ev 导致无从建 g2

对应样例：SCC{1,2,3}（编号 2，val=6）→ SCC{4}（编号 1，val=4）。u=2 时 dp[2]=6，转移给 v=1 得 dp[1]=6+4=10。

运行结果（已用 g++ 实测验证）

输入: 4 5
      1 2 3 4
      1 2
      2 3
      3 1
      3 4
      2 4
输出: 10

说明: 环 1→2→3→1 构成 SCC（Tarjan 编号 2，点权和 6），
      点 4 自成一个 SCC（编号 1，点权 4）
      缩点后唯一边 {1,2,3}→{4}：先转圈拿满 6，再到 4，共 6+4 = 10
      （注意：若样例含边 4→2，则 4→2→3→4 也成环，全图并成一个 SCC）

💡 为什么从 cnt 递减而不是递增？

在 Tarjan 中，先被弹出的分量在缩点图上「更靠后」（更接近汇点）。可以严格证明：若存在边 id[u] → id[v]，则 id[u] > id[v]。

反例（递增遍历为什么错）：设缩点图是一条链 分量3 → 分量2 → 分量1（编号即 Tarjan 出栈顺序）。递增循环先处理分量 1：它此刻 dp 还只是自己的 val（上游分量 3 的贡献还没传到分量 2），却已经被拿去更新下游——最终分量 1 的答案漏掉了分量 3 的点权。这是缩点 DP 最常见的 WA 原因，务必记住：倒着循环，或者老实写一遍拓扑排序。

案例案例3：割点模板（P3388 / B3609 同型）无向图模板

题目：给出 n 个点 m 条边的无向图（不一定连通），求所有割点，按编号升序输出。（1 ≤ n ≤ 2×10⁴，1 ≤ m ≤ 10⁵）

🔍 详细分析过程

第1步：套模板。无向图存边成对添加，DFS 时用边编号跳过反向边（更稳，虽然判割点时「跳过父节点」在无重边题里也常能用）。

第2步：递归前先记 child 数。只有非根节点才用 low 判定；根节点必须在 DFS 结束后单独用 child >= 2 判定。

第3步：注意根的判定写在哪里。必须在 dfs 函数末尾，因为要等所有儿子都数完。

第4步：多连通块。外层循环对每个未访问点当作新根启动一次 DFS。

第5步：复杂度 O(n+m)，答案按编号升序输出即可。

C++割点判定完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 20005, MAXM = 200005;
int n, m, tot = 1, head[MAXN];    // tot 从 1 开始，边从 2 号开始成对编号
struct Edge { int to, nxt; } e[MAXM];
void add(int u, int v) { e[++tot] = {v, head[u]}; head[u] = tot; }

int dfn[MAXN], low[MAXN], tim, cut[MAXN];

void tarjan(int u, int ein) {
    dfn[u] = low[u] = ++tim;
    int child = 0;                   // 统计 DFS 树中 u 的儿子数
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (i == (ein ^ 1)) continue;   // 跳过反向边，重边安全
        if (!dfn[v]) {
            ++child;
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u] && ein != 0)  // 非根判定
                cut[u] = 1;
        } else {
            low[u] = min(low[u], dfn[v]);   // 无向图：回边直接用 dfn
        }
    }
    if (ein == 0 && child >= 2) cut[u] = 1;  // 根单独判定
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        add(u, v); add(v, u);          // 成对添加
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, 0);      // ein = 0 表示 i 是本次 DFS 的根

    vector<int> ans;
    for (int i = 1; i <= n; i++)
        if (cut[i]) ans.push_back(i);
    cout << ans.size() << "\n";
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return 0;
}

🔍 代码逐段解析 · 割点判定模板

1tot=1 的意义：链式前向星边号从 2 开始成对（2↔3、4↔5…），这样 i^1 才恰好是反向边；若 tot 从 0 开始，成对技巧失效

2tarjan(u, ein)：ein 是进入 u 的边号。main 里调用 tarjan(i, 0)，0 是天然哨兵——根没有进入边

3if (i == (ein^1)) continue：只跳过来时那条边的反向边。无向图必须成对 add(u,v)、add(v,u)

4++child：只对「树边」计数，即 DFS 树上 u 的儿子数，回边不算

5low[v] >= dfn[u] && ein != 0：非根割点判据。ein!=0 排除根——根永远满足 low[v]≥dfn[u]，用 low 判会把根全标错

6else low[u]=min(low[u],dfn[v])：无向图只有回边没有横叉边，v 已访问就直接用 dfn[v]，不需要 ins 判断

7if (ein==0 && child>=2)：根割点判定放在函数末尾——必须等所有儿子数完。链状图根只有 1 个儿子，不是割点

8输出：cut[] 按编号升序扫一遍即可，无需排序

9易错点：① 根判定写在循环中间（child 还没数完）；② ein==0 误写成 u==1（多连通块时每个块都有根）；③ 有重边时用 v==fa 跳父必错，必须用边编号

对应样例：树边依次 1→2→3 与 2→4→5→6；回边 3→1、6→4。在 2 处儿子 4 的 low=4≥2 → 2 是割点；在 4 处儿子 5 的 low=4≥4 → 4 是割点；根 1 只有 1 个儿子 → 不是割点。

运行结果

输入: 6 7
      1 2
      1 3
      2 3
      2 4
      3 5
      5 6
      6 3
输出: 2
      2 3

说明: 删掉 2 后 {4} 与 {1,3,5,6} 断开；删掉 3 后 {5,6} 与其余断开

💡 为什么用 ein==0 判断根？

根节点没有「进入边」，因此把进入边的编号设为 0 是一个天然的哨兵。注意链式前向星的第一条边必须是 2 号（tot 初始为 1），否则 0 会与真实边号冲突。同时 i == (ein^1) 里的 ein^1 在 ein==0 时等于 1，而 1 号边不存在，天然安全。

模块 03

实践应用

三道完整题目，从「缩点统计度数」到「割边输出」，覆盖本讲全部考点。

题1受欢迎的牛缩点出度

题目背景

牧场里有 N 头牛，牛与牛之间存在「仰慕」关系（有向的）。如果 A 仰慕 B，且 B 仰慕 C，那么 A 也间接仰慕 C。一头牛被所有其他牛仰慕（直接或间接），它就是「明星牛」。求明星牛的个数。

输入格式

第一行两个整数 N, M（1 ≤ N ≤ 10⁴，1 ≤ M ≤ 5×10⁴）。接下来 M 行，每行两个整数 A, B，表示 A 仰慕 B。

输出格式

一行一个整数，表示明星牛的个数（可能为 0）。

输入样例

3 3
1 2
2 1
2 3

输出样例

数据范围

1 s / 256 MB；N ≤ 10⁴，M ≤ 5×10⁴，保证无自环。

🔍 方法一：Tarjan 缩点 + 出度统计 最优 O(n+m)

关键观察：同一 SCC 内的牛互相仰慕，它们的「受欢迎程度」完全相同，可以缩成一点。

结论（非常重要）：在缩点后的 DAG 中，明星点必须是出度为 0 的分量。若出度不为 0，它指向的那个分量就没有仰慕它，矛盾。

进一步：DAG 中出度为 0 的分量至多只有一个能当明星。若有两个出度为 0 的分量，它们互不可达，答案是 0。

所以算法是：Tarjan 缩点 → 统计每个分量的出度 → 若出度为 0 的分量恰好 1 个，输出它的大小，否则输出 0。

🔍 方法二：对每头牛跑一次 BFS 暴力 O(nm)

对每个点做一次可达性搜索，统计能到达它的点数。n=10⁴、m=5×10⁴ 时是 5×10⁸ 级别，必定超时，只能拿部分分。对比之后，缩点的优势一目了然。

C++受欢迎的牛 —— 完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 10005, MAXM = 50005;
int n, m, tot, head[MAXN];
struct Edge { int to, nxt; } e[MAXM];
void add(int u, int v) { e[++tot] = {v, head[u]}; head[u] = tot; }
int eu[MAXM], ev[MAXM];

int dfn[MAXN], low[MAXN], tim, stk[MAXN], top, ins[MAXN];
int id[MAXN], sz[MAXN], deg[MAXN], cnt;

void tarjan(int u) {
    dfn[u] = low[u] = ++tim;
    stk[++top] = u; ins[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        ++cnt; int v;
        do { v = stk[top--]; ins[v] = 0; id[v] = cnt; sz[cnt]++; }
        while (v != u);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> eu[i] >> ev[i];
        add(eu[i], ev[i]);
    }
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);

    // 统计每个 SCC 的出度（跨分量的边才算）
    for (int i = 1; i <= m; i++)
        if (id[eu[i]] != id[ev[i]]) deg[id[eu[i]]]++;

    int zero = 0, pos = 0;
    for (int i = 1; i <= cnt; i++)
        if (deg[i] == 0) { zero++; pos = i; }

    if (zero == 1) cout << sz[pos] << "\n";   // 唯一汇点，整个分量都是明星
    else cout << 0 << "\n";                // 多个汇点 → 互不可达 → 没有明星
    return 0;
}

🔍 代码逐段解析 · 受欢迎的牛（缩点出度统计）

1Tarjan 求 SCC：与案例 1 完全同款，额外维护 sz[cnt] 记录每个分量的大小（明星牛可能有整团）

2统计出度：重扫 m 条边，id[eu[i]] != id[ev[i]] 时 deg[id[eu[i]]]++——分量内部互相仰慕的边不算出度

3zero/pos 扫描：数出度为 0 的分量个数 zero，并用 pos 记住它（若唯一）

4zero==1 → sz[pos]：DAG 中唯一汇点能被所有分量到达，整团都是明星

5zero≥2 → 0：两个汇点互不可达，不可能有牛被「所有」牛仰慕

6易错点：① 出度统计写在 Tarjan 之前（此时 id 还没算出来）；② 忘记 zero==0 的情形也会走 else 输出 0，逻辑恰好覆盖，无需特判；③ n=1 时唯一分量出度 0，答案是 1

样例 3 3（1→2、2→1、2→3）：SCC{1,2}→{3}，汇点 {3} 出度 0 且唯一，答案 = 1。

运行结果

输入: 3 3
      1 2
      2 1
      2 3
输出: 1

说明: SCC#1 = {1,2}（出度 1，指向 {3}），SCC#2 = {3}（出度 0）
      出度为 0 的分量唯一 → 答案 = 1

💡 换个角度想

如果把题目改成「被所有点可达的点集大小」，就是对缩点图求唯一汇点；如果改成「能到达所有点的点集大小」，那就是求唯一源点（入度为 0 的唯一分量）。这两个结论成对出现，务必一起记住。

题2炸铁路（割边输出）割边模板

题目背景

A 国有一张铁路网（无向连通图）。若某段铁路被炸毁后，整个铁路网不再连通，这段铁路就是「关键铁路」。请找出所有关键铁路。

输入格式

第一行两个整数 n, m（1 ≤ n ≤ 150，1 ≤ m ≤ 5000）。接下来 m 行，每行两个整数 u, v，表示 u 与 v 之间有一段铁路。

输出格式

按 u 从小到大输出所有关键铁路，每行一条；同一 u 时按 v 从小到大。输出格式为 u v，要求 u < v。

输入样例

6 6
1 2
2 3
2 4
3 5
4 5
5 6

输出样例

1 2
5 6

数据范围

1 s / 128 MB。注意图中可能有重边。

🔍 分析

建模：「关键铁路」= 割边（桥）。1→2 是桥（{1} 只能通过它出去），5→6 是桥（{6} 只能通过它进来），其余都在环 2-3-5-4-2 上，不是桥。

重边处理：必须用边编号法，i == (ein ^ 1) 跳过唯一反向边。若误用「跳过父节点」，重边会被当成父边跳过，答案错误。

输出排序：遍历所有正向边，若 bridge[i] 为真则记录 (e[i^1].to, e[i].to)（因为每条无向边存了两份，只看正向避免重复）。为满足「u 优先、v 次之」的字典序，把所有桥存进 vector 后 sort 即可。

复杂度：O(n+m)，n 只有 150，随便过。

C++炸铁路 —— 完整代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 155, MAXM = 10005;
int n, m, tot = 1, head[MAXN], dfn[MAXN], low[MAXN], tim;
struct Edge { int to, nxt; } e[MAXM];
int bridge[MAXM];
void add(int u, int v) { e[++tot] = {v, head[u]}; head[u] = tot; }

void tarjan(int u, int ein) {
    dfn[u] = low[u] = ++tim;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (i == (ein ^ 1)) continue;      // 跳过反向边（重边安全）
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])            // 严格大于：割边
                bridge[i] = bridge[i ^ 1] = 1;
        } else low[u] = min(low[u], dfn[v]);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        if (u > v) swap(u, v);              // 统一成 u < v 便于输出
        add(u, v); add(v, u);
    }
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0);

    vector<pair<int,int>> ans;
    for (int i = 2; i <= tot; i += 2)               // 只看正向边，避免重复
        if (bridge[i]) ans.push_back({e[i ^ 1].to, e[i].to});
    sort(ans.begin(), ans.end());
    for (auto& p : ans) cout << p.first << " " << p.second << "\n";
    return 0;
}

🔍 代码逐段解析 · 炸铁路（割边模板）

第 1~4 行（数据结构） —— tot=1 让边从 2 号开始成对编号；bridge[i] 标记 i 号边是否为桥，标记时 i 与 i^1 一起置 1。

tarjan 函数 —— 与割点模板几乎相同，只是非根判定换成了 low[v] > dfn[u]（严格大于）。注意这里不需要 child 计数，因为割边没有「根特殊规则」。

读入的 swap —— if (u > v) swap(u,v) 统一成小号在前，保证输出格式 u < v；对建图无影响（无向边存两份）。

收集答案 —— 只扫正向边 i = 2, 4, 6, …, tot；e[i^1].to 恰是这条边的起点（成对存边的性质），所以 {e[i^1].to, e[i].to} 就是桥的两个端点，最后 sort 满足字典序输出。

易错点 —— ① 统计时对 i 从 1 扫到 tot，每条桥被数两遍；② 忘记 sort，输出顺序不合规；③ 重边题若误用 v==fa 跳父，重边会被误判成桥。

运行结果

💡 反向边的两个用途

成对存边时，边 i 的反向边是 i^1，且 e[i^1].to 恰好是这条边的起点。所以「只看正向边再取 e[i^1].to 当起点」是查询无向边端点的经典技巧，值得抄进笔记。

题3割点与子树规模综合

题目背景

给定一张 n 个点的无向连通图（n ≤ 10⁵，m ≤ 5×10⁵）。对每个点 u，求删去 u 后图中新增的有序点对数（即原本连通、删后不再连通的点对数量）。

输入格式

第一行两个整数 n, m。接下来 m 行每行两个整数 u, v。

输出格式

n 行，第 i 行输出删去点 i 后的答案。

输入样例

5 5
1 2
2 3
3 1
3 4
4 5

输出样例

4
4
8
4
4

数据范围

1 s / 128 MB。答案可能超过 int，请用 long long。

🔍 分析（POI2008 BLO 的思想）

核心：删去 u 后，与 u 相连的各个「会被切断的子树块」彼此断开，再加上「除这些子树与 u 之外的其余部分」这一大块，它们两两之间原本可达，删后不可达。

记 sz[v] 为 DFS 树上 v 子树的大小，sum = 所有满足 low[v] ≥ dfn[u] 的儿子的 sz 之和，rest = n - 1 - sum。

答案由三部分组成：
① 每个「会被切断的子树」与「其余所有点」构成的点对：Σ sz[v] × (n - sz[v])；
② 剩下的那块与 sum 之间：rest × (1 + sum)；
③ u 自身与其余 n-1 个点：n - 1。

实现要点：在 Tarjan 回溯时顺便统计 sz[u]，并在 low[v] >= dfn[u] 成立时立刻累加 sz[v] * (n - sz[v])。非割点时第①项自然为 0，答案退化为 n-1。

复杂度：O(n+m)，一次 DFS 完成。

C++删点连通性统计 —— 核心代码

int dfn[MAXN], low[MAXN], tim, sz[MAXN];
long long ans[MAXN];

void tarjan(int u, int ein) {
    dfn[u] = low[u] = ++tim;
    sz[u] = 1;
    long long sum = 0;                  // 会被切掉的子树总规模
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (i == (ein ^ 1)) continue;
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            sz[u] += sz[v];
            if (low[v] >= dfn[u]) {      // v 子树会被切断
                ans[u] += 1LL * sz[v] * (n - sz[v]);
                sum += sz[v];
            }
        } else low[u] = min(low[u], dfn[v]);
    }
    long long rest = n - 1 - sum;          // 除 u 与这些子树外剩下的部分
    ans[u] += 1LL * rest * (1 + sum);
    ans[u] += n - 1;                       // u 自身
}

🔍 代码逐段解析 · 删点连通性统计（BLO 核心代码）

sz[u]=1 与回溯累加 —— 进入时子树大小为 1，sz[u] += sz[v] 在回溯时汇总，一趟 DFS 顺手算出整棵子树规模。

sum 变量 —— 局部变量，累加 u 的所有「会被切断的儿子子树」总规模；它是函数栈上的临时量，不同层互不干扰。

①项 sz[v]*(n-sz[v]) —— 注意是 n 而非 n-1：这里统计的是有序点对，被切断的子树 v 与「其余所有点（含 u 自己）」之间的有序对数，稍后被 ③ 项巧妙补齐（详见下方验证）。

②项 rest*(1+sum) —— 剩余部分 rest 与「被切子树 sum + u 自己（1）」之间的有序点对；rest 里的点相互仍连通，不再产生断裂。

③项 n-1 —— u 与其余每个点各贡献一对（有序即一个方向），任何点删掉后都至少断 n-1 对。

易错点 —— ① 乘法必须 1LL * 转 long long，n=10⁵ 时 sz*(n-sz) 约 10¹⁰ 会爆 int；② sum 要用局部变量而不是全局；③ 根节点走同一套公式也正确（此时 rest=0，①项自动退化为 n-1）。

运行结果（已用 g++ 实测验证，有序点对口径）

输入: 5 5
      1 2
      2 3
      3 1
      3 4
      4 5
输出: 8
      8
      16
      14
      8

说明: 删 1/2/5：只剩自己的 n-1=4 对无序点对，有序即 8 对
      删 3：{1,2} 与 {4,5} 之间 2*2*2=8 对有序点对断裂，加上 3 与
            其余 4 点的 8 对，共 16
      删 4：{5} 与 {1,2,3,4} 之间 1*4*2=8 对，加上 4 与其余 4 点的
            8 对，共 14（注意 {5} 与 {1,2,3} 也被切断）

💡 从「判割点」升级到「量化影响」

割点题的最高级形态不是「找出割点」，而是「算出删掉它之后世界变得多糟」。把 sz[] 和判据结合，就能在同一个 DFS 里答出这类问题，这是 CSP-S 图论题非常喜欢的方向。

模块 04

总结提升

①核心要点与万能模板

知识板块	必须记住的核心
dfn / low	dfn 进入时间；low = 子树能回到的最小 dfn
有向图 SCC	仅当 `ins[v]` 为真时才用 dfn[v] 更新 low
出栈条件	`low[u]==dfn[u]` → 弹栈至 u，弹出一组即一个 SCC
缩点	跨分量边构成 DAG；编号是逆拓扑序，DP 从大到小
割点判定	非根：`low[v]≥dfn[u]`；根：孩子数 ≥ 2
割边判定	`low[v]>dfn[u]`；重边用边编号 `i==(ein^1)` 处理
边双 / 点双	边双 = 删桥后的连通块；点双 = 边栈划分，割点可属于多个
复杂度	全部 O(n+m)，一次 DFS 搞定

C++万能 Tarjan 模板（有向 SCC + 无向割点割边三合一）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005, MAXM = 500005;
int n, m, tot = 1, head[MAXN];
struct Edge { int to, nxt; } e[MAXM];
int dfn[MAXN], low[MAXN], tim,
    stk[MAXN], top, ins[MAXN], id[MAXN], cnt;   // 有向图用
int cut[MAXN], bridge[MAXM];                   // 无向图用

void add(int u, int v) { e[++tot] = {v, head[u]}; head[u] = tot; }
void add2(int u, int v) { add(u, v); add(v, u); }

/* ===== 有向图：强连通分量 ===== */
void scc(int u) {
    dfn[u] = low[u] = ++tim;
    stk[++top] = u; ins[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dfn[v]) { scc(v); low[u] = min(low[u], low[v]); }
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        ++cnt; int v;
        do { v = stk[top--]; ins[v] = 0; id[v] = cnt; } while (v != u);
    }
}

/* ===== 无向图：割点 + 割边（一次 DFS 同时求）===== */
void cutTarjan(int u, int ein) {
    dfn[u] = low[u] = ++tim;
    int child = 0;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (i == (ein ^ 1)) continue;              // 只跳过一条反向边
        if (!dfn[v]) {
            ++child;
            cutTarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u] && ein) cut[u] = 1;              // 非根割点
            if (low[v] > dfn[u]) bridge[i] = bridge[i ^ 1] = 1;  // 割边
        } else low[u] = min(low[u], dfn[v]);
    }
    if (!ein && child >= 2) cut[u] = 1;               // 根割点
}

🔍 代码逐段解析 · 万能 Tarjan 模板（三合一）

共用部分 —— dfn/low/stk/ins/id/cnt 全部共用；tot=1 是为无向图成对边准备的，有向图场景它无害（1 号空边永远不被访问）。

scc(u)（有向） —— 三要素：入栈打 ins、回边 else if (ins[v]) 用 dfn[v]、low[u]==dfn[u] 时 do-while 弹栈赋 id。有向图不需要 ein 参数（没有成对反向边要跳）。

cutTarjan(u, ein)（无向） —— 割点与割边在同一次 DFS 里结算：low[v] ≥ dfn[u] && ein 标割点（非根），low[v] > dfn[u] 标割边（两个条件相差的正是等号）；循环结束后 !ein && child ≥ 2 补判根割点。

使用姿势 —— 有向题调用 scc；无向题成对 add2 后调用 cutTarjan(i, 0)；两套函数不要混用（有向图判割点无意义，无向图判 SCC 需要边双而非点双）。

易错点 —— ① 多组数据必须清空 dfn/low/ins/tim/cnt/head/cut/bridge；② cutTarjan 里若只求割边，child 与根判定可整体省略；③ bridge 数组开 MAXM（边数两倍空间）而不是 MAXN。

🔑 一句话总纲

有向判栈、无向判边；≥ 是割点、> 是割边；根看孩子数、重边看编号。

②拓展案例

拓展1缩点 + 度数统计

校园网 Network of Schools：给一个有向图，求①最少从几个点出发能覆盖全图；②最少加几条边使全图强连通。

查看参考答案

思路（缩点后只看度数）：

① 缩点后统计入度为 0 的分量个数，即为答案（每个源点必须被单独下发一份软件）。

② 设入度为 0 的分量数 a，出度为 0 的分量数 b。答案 = max(a, b)。特判：若缩点后只有 1 个分量（原图已强连通），答案为 0。

int a = 0, b = 0;
for (int i = 1; i <= cnt; i++) {
    if (indeg[i] == 0) a++;
    if (outdeg[i] == 0) b++;
}
if (cnt == 1) cout << "1\n0\n";    // 特判：已经强连通
else cout << a << "\n" << max(a, b) << "\n";

运行结果：5 个点 5 条边 2 4 / 3 4 / 1 2 / 4 5 / 3 5 → 输出 2 与 2。

考点：SCC 缩点后「源点 = 入度 0，汇点 = 出度 0」这一对偶结论，以及 cnt==1 的边界特判。忘特判会输出 1 1 而不是 1 0。

拓展2点双连通分量应用

矿场搭建：在无向图中选最少的点建救援出口，使得删去任意一个点后，各个连通块中仍有出口可达。

查看参考答案

思路（点双 + 分类讨论）：先求所有点双连通分量，再按分量内割点个数分类：

① 割点数 = 0（整图就是一个双连通块）：需要 2 个出口，方案数为 sz*(sz-1)/2。

② 割点数 = 1：这个分量只通过一个割点与外界相连，割点一挂它就与世隔绝，因此必须在分量内部的非割点中建 1 个出口，方案数 × (sz - 1)。

③ 割点数 ≥ 2：删掉其中任一割点，这个分量仍能通过另一个割点逃到别的分量，不需要建出口。

long long ways = 1; int need = 0;
for (int i = 1; i <= bccCnt; i++) {
    int cutCnt = 0;
    for (int x : bcc[i]) if (cut[x]) cutCnt++;
    int s = bcc[i].size();
    if (cutCnt == 0) { need += 2; ways *= 1LL * s * (s - 1) / 2; }
    else if (cutCnt == 1) { need += 1; ways *= 1LL * (s - 1); }
}
cout << need << " " << ways << "\n";

运行结果（已验证）：7 个点 9 条边——三个三角形依次共用割点串成链：1-2-3 / 3-4-5 / 5-6-7（即边 12,23,31,34,45,53,56,67,75）→ 输出 2 4。三个点双中，首尾两个各含 1 个割点（各建 1 个出口、方案 ×2），中间的含 2 个割点（不用建）；出口数 1+1=2，方案数 2×2=4。

考点：点双分类讨论 + 乘法原理计数。易错：把 (sz-1) 写成 sz，漏掉「割点本身不能建出口」这一约束。

拓展3边双缩点成树

Redundant Paths：求最少加几条边，使一张无向连通图变成边双连通图。

查看参考答案

思路：① Tarjan 标记所有割边；② 删掉割边后对连通块染色，得到若干边双；③ 把每个边双缩成一点，桥就是树边，得到一棵树。

设这棵树中度数为 1 的叶子有 leaf 个，答案 = (leaf + 1) / 2。

为什么？每加一条边最多让两个叶子摆脱「度 1」的困境，所以至少需要 ceil(leaf/2)；而把叶子两两配对连边总是可达的，所以这个下界可以取到。

// 步骤1：染色（跳过割边）
void color(int u, int c) {
    col[u] = c;
    for (int i = head[u]; i; i = e[i].nxt)
        if (!bridge[i] && !col[e[i].to]) color(e[i].to, c);
}
// 步骤2：统计缩点树上每个分量的度数
for (int i = 2; i <= tot; i += 2)
    if (bridge[i]) {
        deg[col[e[i ^ 1].to]]++;
        deg[col[e[i].to]]++;
    }
int leaf = 0;
for (int i = 1; i <= colCnt; i++) if (deg[i] == 1) leaf++;
cout << (leaf + 1) / 2 << "\n";

运行结果（已验证）：7 个点 7 条边：三角形 1-2-3，三条桥 1-4 / 2-5 / 3-6，再加边 4-7 → 边双缩点后 T1 与 {4,7}、{5}、{6} 相连，叶子 3 个 → 输出 2。

易错：把 (leaf+1)/2 写成 leaf/2，叶子数为奇数时答案偏小 1。

③思考与启发

💡 思考一：Tarjan 为什么能在一次 DFS 里同时干这么多事？

展开参考

因为 dfn/low 描述的是一棵 DFS 树的拓扑结构，而 SCC、割点、割边本质上都是「删掉某个点/边后连通性如何变化」的问题——这恰好可以翻译成「子树能否绕过某个祖先向上连」。

统一视角：low[v] 与 dfn[u] 的大小关系就是一切判据的源头。low[v] < dfn[u] → v 能绕过 u 向上走，不构成割点；low[v] = dfn[u] → v 刚好只能到达 u，是割点但不是割边；low[v] > dfn[u] → v 连 u 都到不了，边 (u,v) 是割边。三条判据其实是同一个不等式的三个区间。

💡 思考二：为什么缩点后的图是 DAG？如果原图还有重边怎么办？

展开参考

DAG 的证明（反证）：假设缩点图上存在环 C → C₁ → … → C，那么按强连通的定义，C 与 C₁ 之间互相可达，它们本该在同一个 SCC 里，矛盾。所以缩点图必无环。

重边：缩点后 id[u] → id[v] 可能有多条重边（原图中 u,v 间有多条边，或不同点对映射到同一对分量）。对于「最长路 / 最短路」类 DP，重边完全无害（取 max/min 幂等）；但若题目统计路径条数，就必须去重——常用办法是对重构图用 set 存边，或排序后 unique。

💡 思考三：二分图判定和割点判定，哪个更难？

展开参考

❌ 错误

for (int u = 1; u <= cnt; u++) for (int v : g2[u]) dp[v] = max(dp[v], dp[u] + val[v]); 递增遍历，用未算好的 dp[u] 去更新别人。

✅ 正确

Tarjan 编号是逆拓扑序：for (int u = cnt; u >= 1; u--)。或者老实在缩点图上跑一遍拓扑排序再 DP。

口诀：Tarjan 编号反着走，或者拓扑排一排再下手！

📋Tarjan 家族速查表

问题	关键判据	额外结构	复杂度
有向图 SCC	low[u] == dfn[u]	节点栈 + ins 标记	O(n+m)
缩点	id[u] != id[v] 时连边	新图 g2	O(n+m)
无向图割点	low[v] ≥ dfn[u]（非根） child ≥ 2（根）	child 计数	O(n+m)
无向图割边	low[v] > dfn[u]	成对边编号	O(n+m)
点双分量	low[v] ≥ dfn[u] 时弹边栈	边栈	O(n+m)
边双分量	删掉所有割边后染色	col 数组	O(n+m)

📌笔记卡

📖 必记概念

dfn = 进入时间戳；low = 子树可达最小 dfn
SCC = 极大的两两可达点集
缩点后必为 DAG
割点：删点断图；割边：删边断图
点双割点可重复，边双是划分

🧠 必背模板

有向：else if(ins[v]) low[u]=min(low[u],dfn[v]);
出栈：if(low[u]==dfn[u]) do-while 弹栈
割点：low[v]>=dfn[u] && ein
割边：low[v]>dfn[u]
重边：if(i==(ein^1)) continue;

⚠️ 考场提醒

图不一定连通，外层必须循环每个未访问点
多组数据要清空 dfn/low/ins/tim/cnt/head
链式前向星 tot 初始化为 1
缩点 DP 从 cnt 递减，别写反
答案可能爆 int，点对计数用 long long

课后练习

分层练习作业

A基础 / B提高 / C挑战，难度递增。C组后附 12 道洛谷原题。

🟢 A组 · 基础（4题）

A1概念辨析

有向图 G 有 5 个点、4 条边：1→2、2→3、3→1、3→4。写出它的所有强连通分量与缩点后的边集。

查看参考答案

思路：先找环 1→2→3→1，这三个点两两可达，构成 SCC。4 只有入边没有出边，是单独一个 SCC。

答案：SCC = {1,2,3} 与 {4}。缩点后只有一条边：{1,2,3} → {4}。

考点：强连通分量的「极大」含义；缩点后图必为 DAG。

易错：把 {4} 也并进前一个分量——4 无法回到 1，不满足两两可达。孤立点或单纯「只进不出」的点自己就是一个 SCC。

A2模板默写

默写有向图 Tarjan 求 SCC 的完整函数（含入栈、low 更新、出栈三个要点）。

查看参考答案

void tarjan(int u) {
    dfn[u] = low[u] = ++tim;
    stk[++top] = u; ins[u] = 1;              // ① 入栈
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
        else if (ins[v]) low[u] = min(low[u], dfn[v]);   // ② low 更新
    }
    if (low[u] == dfn[u]) {                    // ③ 出栈
        ++cnt; int v;
        do { v = stk[top--]; ins[v] = 0; id[v] = cnt; } while (v != u);
    }
}

考点：三个要点缺一不可。易错：把 ins[v] 写成 !ins[v]，或把 do-while 写成先判后弹的 while 造成死循环。

A3手工模拟

对下图手工跑一遍割点算法，列出每个点的 dfn 与 low：1-2、2-3、3-1、2-4、4-5、5-6、6-4。判断哪些点是割点。

查看参考答案

第1步：DFS 从 1 出发。dfn[1]=1, dfn[2]=2, dfn[3]=3（3 有回边到 1，low[3]=1），回溯 low[2]=1，low[1]=1。

第2步：走 2→4。dfn[4]=4, dfn[5]=5, dfn[6]=6（6 有回边到 4，low[6]=4），回溯 low[5]=4，low[4]=4。

第3步：判定。在 2 处：儿子 3 的 low[3]=1 ≥ dfn[2]=2？不满足（1 < 2）；儿子 4 的 low[4]=4 ≥ dfn[2]=2？满足 → 2 是割点（删 2 后 {4,5,6} 与 {1,3} 断开）。

在 4 处：儿子 5 的 low[5]=4 ≥ dfn[4]=4？满足 → 4 是割点（删 4 后 {5,6} 与其余断开）。

答案：割点为 2 和 4。

易错：忘记 3 的回边使 low[3]=1，从而误判 2 不是割点，或把 1、3 也算进去。

A4编程题

给定 n 个点 m 条边的有向图，输出强连通分量的个数（n ≤ 10⁴，m ≤ 5×10⁴）。

查看参考答案

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005, MAXM = 50005;
int n, m, tot, head[MAXN], dfn[MAXN], low[MAXN], tim;
int stk[MAXN], top, ins[MAXN], cnt;
struct Edge { int to, nxt; } e[MAXM];
void add(int u, int v) { e[++tot] = {v, head[u]}; head[u] = tot; }

void tarjan(int u) {
    dfn[u] = low[u] = ++tim;
    stk[++top] = u; ins[u] = 1;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) { ++cnt; int v;
        do { v = stk[top--]; ins[v] = 0; } while (v != u); }
}
int main() {
    cin >> n >> m;
    for (int i = 1, u, v; i <= m; i++) { cin >> u >> v; add(u, v); }
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
    cout << cnt << endl;
}

代码逐段解析：建图与 main 循环同前；tarjan 里本题只需 cnt——每次 low[u]==dfn[u] 触发弹栈时 ++cnt，分量内点无需 id，弹栈只为清 ins 标记。外层 if(!dfn[i]) tarjan(i) 保证不连通图每个块都被统计。

易错：① 外层忘记对每个未访问点启动 DFS，不连通图只统计到第一个块；② 忘了 stk[++top]=u 压栈，出栈时越界；③ cnt 误放在循环里而非弹栈处，数量虚高。

🟡 B组 · 提高（4题）

B1缩点应用

消息扩散：n 个点的有向图，最少需要把消息告诉几个点，才能让所有点都知道（消息沿有向边传播）。

查看参考答案

思路：先 Tarjan 缩点。缩点后的 DAG 中，入度为 0 的分量没有任何点能到达它，所以必须手动告诉它——每个入度 0 的分量至少选 1 个点。而只要把所有入度 0 的分量都点了，其他分量必定能被传播到（否则它也会是入度 0）。

答案 = 缩点后入度为 0 的分量个数。

int ans = 0;
for (int i = 1; i <= cnt; i++)
    if (indeg[i] == 0) ans++;
cout << ans << endl;

运行结果：输入 4 3 / 1 2 / 2 3 / 3 4 → 输出 1。

易错：把入度统计写在 Tarjan 之前（此时还没有 id，无法判断同分量边）；或忘掉「同一分量内的边不算入度」。

B2割边应用

给定无向连通图（含重边），输出所有割边的数量与编号（按输入顺序）。

查看参考答案

int tot = 1, head[MAXN], dfn[MAXN], low[MAXN], tim, bridge[MAXM];
struct Edge { int to, nxt; } e[MAXM];
void add(int u, int v) { e[++tot] = {v, head[u]}; head[u] = tot; }

void tarjan(int u, int ein) {
    dfn[u] = low[u] = ++tim;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (i == (ein ^ 1)) continue;
        if (!dfn[v]) {
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) bridge[i] = bridge[i ^ 1] = 1;
        } else low[u] = min(low[u], dfn[v]);
    }
}

验证样例：4 个点、5 条边 1 2 / 2 3 / 3 1 / 2 4 / 2 4（最后两条为重边）→ 割边只有 2 4 这一对，数量 1。

易错：用「跳过父节点」导致重边 (2,4) 被误判成桥，答案变成 2；或统计时忘了把 bridge[i^1] 一起置位。

B3边双缩点

把无向连通图按边双连通分量缩点，输出新图的点数与边数。

查看参考答案

思路：① Tarjan 标桥；② 跳过桥做一次 DFS 染色，得到 col[u]；③ 新图点数 = 染色数，新图边数 = 割边数。

void color(int u, int c) {
    col[u] = c;
    for (int i = head[u]; i; i = e[i].nxt)
        if (!bridge[i] && !col[e[i].to]) color(e[i].to, c);
}
// 主逻辑
int cc = 0, be = 0;
for (int i = 1; i <= n; i++) if (!col[i]) color(i, ++cc);
for (int i = 2; i <= tot; i += 2) if (bridge[i]) be++;
cout << cc << " " << be << endl;

运行结果：六个点构成「三角形 - 桥 - 三角形」结构（共 7 条边）→ 输出 2 1。

易错：染色时忘记跳过割边，导致所有点被染成一色；或 count 时把每条桥数了两遍（正向 + 反向），得到 2 倍答案。

B4割点 + 计数

统计无向图中割点的个数，并按升序输出它们的编号（图可能不连通）。

查看参考答案

void tarjan(int u, int ein) {
    dfn[u] = low[u] = ++tim;
    int child = 0;
    for (int i = head[u]; i; i = e[i].nxt) {
        int v = e[i].to;
        if (i == (ein ^ 1)) continue;
        if (!dfn[v]) {
            ++child; tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u] && ein) cut[u] = 1;
        } else low[u] = min(low[u], dfn[v]);
    }
    if (!ein && child >= 2) cut[u] = 1;
}
// 外层：for (i=1..n) if(!dfn[i]) tarjan(i,0);

// 缩点后建图 g2，val[c] = 分量金额和，bar[c] = 分量内是否有酒吧
for (int i = 1; i <= cnt; i++) dp[i] = -1e18;   // 初始不可达
dp[id[S]] = val[id[S]];
for (int u = cnt; u >= 1; u--) {                  // 逆拓扑序
    if (dp[u] < 0) continue;                        // 从 S 出发到不了，跳过
    for (int v : g2[u]) dp[v] = max(dp[v], dp[u] + val[v]);
}
long long ans = 0;
for (int i = 1; i <= cnt; i++)
    if (bar[i]) ans = max(ans, dp[i]);
cout << ans << endl;

运行结果（已验证）：6 个点 7 条边：1→2 / 2→3 / 3→1 / 3→4 / 4→5 / 5→6 / 6→4，S=1，酒吧在点 6，各点金额依次 1~6 → 缩点后分量 {1,2,3}（权 6）→ {4,5,6}（权 15，含酒吧），dp 传播得 21。

易错：把 dp 全部初始化成 val[i]（相当于可以从任意点出发），导致从不可达分量传播出错误答案；或答案遍历时忘了只统计含酒吧的分量。

C4构造与证明

证明：一个有 n 个点、m 条边的无向连通图，割边的数量不超过 n-1。

查看参考答案

证明（缩点法）：把所有边双连通分量缩成一个点。缩点之后，原来的每条割边都变成新图的一条边，而每个非割边都在某个边双内部被「吸收」了。

由边双连通的性质，缩点后的新图是一棵树（连通且无环：若新图有环，环上任意两点就有两条边不相交路径，与割边矛盾）。

一棵有 k 个节点的树恰有 k-1 条边。而 k ≤ n（每个边双至少含 1 个点），所以割边数 = k-1 ≤ n-1。证毕。

等号成立条件：当且仅当原图就是一棵树（每个边双只含 1 个点）。

考点：「割边集 = 边双缩点树的边集」这一结构性结论，是很多难题的出发点。

🏆 洛谷原题精选（12道）

以下 12 道题全部围绕强连通分量、割点、割边与双连通分量，按难度从普及+到提高排列。

P2863
The Cow Prom S（SCC 计数）普及+

P1656
炸铁路（割边模板）普及+

P2002
消息扩散（缩点入度）普及+

P3388
【模板】割点（割顶）提高

P2341
受欢迎的牛 G（缩点 + 出度）提高

P3387
【模板】缩点（DAG 最长路）提高

B3609
【图论与代数结构 501】割点提高

P2746
校园网 Network of Schools提高

P3469
BLO-Blockade（割点 + 子树）提高

P5058
嗅探器（割点应用）提高

P3225
矿场搭建（点双分类讨论）提高

P8436
【模板】边双连通分量提高

情景导航

连体城堡 = SCC

独木桥 = 割边

交通枢纽 = 割点

蜘蛛网 = 双连通

知识探究

dfn[u]

low[u]

回溯合并

✅ 正确写法

❌ 常见错误

缩点：把强连通块「捏」成一个点 必掌握

❌ 用父节点判重（会被重边坑）

✅ 用边的编号判重（推荐）

🧩 边双连通分量 (e-BCC)

🧩 点双连通分量 (v-BCC)

💡 边界思考

💡 为什么从 cnt 递减而不是递增？

💡 为什么用 ein==0 判断根？

实践应用

题目背景

输入格式

输出格式

输入样例

输出样例

数据范围

💡 换个角度想

题目背景

输入格式

输出格式

输入样例

输出样例

数据范围

💡 反向边的两个用途

题目背景

输入格式

输出格式

输入样例

输出样例

数据范围

💡 从「判割点」升级到「量化影响」

总结提升

校园网 Network of Schools：给一个有向图，求①最少从几个点出发能覆盖全图；②最少加几条边使全图强连通。

矿场搭建：在无向图中选最少的点建救援出口，使得删去任意一个点后，各个连通块中仍有出口可达。

Redundant Paths：求最少加几条边，使一张无向连通图变成边双连通图。

💡 思考一：Tarjan 为什么能在一次 DFS 里同时干这么多事？

💡 思考二：为什么缩点后的图是 DAG？如果原图还有重边怎么办？

💡 思考三：二分图判定和割点判定，哪个更难？

学习检测

low 更新用错对象（有向图）

根的割点判定漏写或写错

割边判定写成 >=

重边把「真桥」变成「假桥」

缩点后 DP 方向反了

📖 必记概念

🧠 必背模板

⚠️ 考场提醒

分层练习作业

🟢 A组 · 基础（4题）

有向图 G 有 5 个点、4 条边：1→2、2→3、3→1、3→4。写出它的所有强连通分量与缩点后的边集。

默写有向图 Tarjan 求 SCC 的完整函数（含入栈、low 更新、出栈三个要点）。

对下图手工跑一遍割点算法，列出每个点的 dfn 与 low：1-2、2-3、3-1、2-4、4-5、5-6、6-4。判断哪些点是割点。

给定 n 个点 m 条边的有向图，输出强连通分量的个数（n ≤ 10⁴，m ≤ 5×10⁴）。

🟡 B组 · 提高（4题）

消息扩散：n 个点的有向图，最少需要把消息告诉几个点，才能让所有点都知道（消息沿有向边传播）。

给定无向连通图（含重边），输出所有割边的数量与编号（按输入顺序）。

把无向连通图按边双连通分量缩点，输出新图的点数与边数。

统计无向图中割点的个数，并按升序输出它们的编号（图可能不连通）。

🔴 C组 · 挑战（4题）

在一个有向图中，若存在边 u→v，则关于 Tarjan 算法求出的 SCC 编号 id，下列哪一项一定成立？

给定一张无向图，问：能否删去恰好一条边使图不连通？如果原图本身不连通呢？

抢掠计划：有向图有 n 个点 m 条边，每个点有金额 a[u]。从起点 S 出发，沿有向边移动，最终可以停在任意一个「酒吧点」上。求最多能抢到多少钱（重复经过的点只算一次）。

证明：一个有 n 个点、m 条边的无向连通图，割边的数量不超过 n-1。

🏆 洛谷原题精选（12道）

缩点：把强连通块「捏」成一个点必掌握