连通图、强连通图与双连通图 | 王心俊老师信息学奥赛课件

模块 01

情景导航

从一次「机房断网事故」出发，理解连通性为什么值钱 —— 它决定了图上很多问题是「可解」还是「无解」。

故事断网的机房

学校信息中心有 12 台服务器，之间用网线互相连接。网络管理员小周遇到了三件事。

第一件事：单向链路。他们把部分链路换成了「单向光纤」（A 能发给 B，B 不能回发给 A）。有天半夜，运维同学发现从管理终端 A 能访问到服务器 B，但从 B 死活连不上 A。小周意识到：无向图里「连通」是相互的，有向图里却出现了「单向可达」——这就要区分可达与强连通。

第二件事：单点故障。某台核心交换机重启了，结果整个机房分成了两半，谁也连不上谁。小周画图后发现：这台机器是整张图的割点，一拔掉，图就断开。

第三件事：单线故障。更巧的是，某根主干网线被施工挖断了，同样导致网络分裂。这根线就是桥——它不是点的问题，而是边的问题。

小周翻开教材，看到一句话：「无向图论连通性，有向图论强连通，再按『删点还是删边会断』分出点双与边双。」 他恍然大悟：原来这些名词是在回答三个完全不同的问题。

连通性 = 在问「图有多结实」；割点/桥 = 在找「哪里最脆弱」。

💡 故事背后的算法思想

「互相可达」是等价关系：若 u 能到 v、v 能到 u，且 v 能到 w、w 能到 v，那么 u 也必然能到 w（u→v→w）且 w 能到 u（w→v→u）。所以「强连通」把有向图的点划分成若干个强连通分量 (SCC)，每个分量内部完全互通。

缩点把环抱成团：把每个 SCC 压缩成一个点，得到的图一定不含环 —— 也就是 DAG。这样上一讲学的拓扑排序 + DAG DP 就能派上用场。这就是「SCC + 缩点」为什么是竞赛里的万能起手式。

双连通刻画「抗打击能力」：点双连通要求删掉任意一个点仍连通（无割点），边双连通要求删掉任意一条边仍连通（无桥）。把它们拆成块之后，图的「韧性」就变成一棵树，可以拿来做树上 DP。

①生活类比

🛣️

城市道路 = 无向连通

两个小区之间通常有往返道路，只要路网接通就能互相到达。

→ 连通分量

🚦

单行道 = 有向强连通

老城区全是单行道，A 能开到 B 不代表 B 能开回 A；绕一圈能回去才算强连通。

→ SCC

🌉

独木桥 = 桥

两座岛之间只靠一座桥相连，桥一断就彻底隔绝 —— 这条边就是桥。

→ 边双连通

🚉

唯一中转站 = 割点

两个城区只有一班公交经停同一站点，这个站点一旦停运，两区就失联。

→ 点双连通

②核心定义

连通分量 (Connected Component)：无向图中，若 u 与 v 之间存在路径，则称二者连通。「连通」是等价关系，据此把点划分出的等价类称为连通分量。

强连通分量 (SCC, Strongly Connected Component)：有向图中，若点集 S 内任意两点 u, v 都满足「u 可达 v 且 v 可达 u」，则称 S 为强连通分量。

割点 (Cut Vertex)：无向图中，删去点 u 以及所有与 u 相连的边后，图的连通块数增加，则 u 是割点。

桥 (Bridge)：无向图中，删去边 e 后连通块数增加，则 e 是桥（割边）。

点双连通 / 边双连通：不存在割点的连通图称点双连通图；不存在桥的连通图称边双连通图。点双连通分量（v-BCC）是「点双极大的子图」，边双连通分量（e-BCC）是「边双极大的子图」。

📌 本讲核心知识地图

板块	核心内容	对应大纲
连通图	无向图等价类划分、BFS/DFS 求连通块	连通图与强连通图【7】
强连通图	有向图双向可达、正反两次 DFS 判定	连通图与强连通图【7】
双连通图	割点 / 桥、点双 / 边双分量	双连通图【7】
Tarjan 预览	dfn 时间戳 + low 回溯值	为 s5-15 铺垫
缩点成树	e-BCC 缩点后得到一棵树	树上问题的预处理

③核心口诀

🔑 连通三兄弟

无向图看连通分量，有向图看强连通分量，抗打击看双连通分量。

🔑 割点与桥

删点断图是割点，删边断图是桥；割点天生属于多个点双，桥天生不属于任何环。

🔑 Tarjan 心法

dfn 记「第几个被访问」，low 记「顺着子树能回溯到的最小 dfn」；low 回不去，就说明这里是唯一的通路。

模块 02

知识探究

先把「连通」的三种尺度讲清楚，再看它们的判定与分解算法。

1连通图与强连通图基础

无向图：若任意两点间都有路径，称图为连通图；否则图的点被划分为若干连通分量。用一次 DFS/BFS 就能求出所有连通分量，O(n+m)。

有向图：可达性是单向的。若任意两点互相可达，称图为强连通图。有向图一定可以唯一划分为若干 SCC。

🔗 无向图连通性

可达性对称：u 能到 v ⟺ v 能到 u
「连通」是等价关系（自反、对称、传递）
一次 DFS 即可划出所有连通块
连通块数 = 做 DFS 的外层启动次数

🚦 有向图强连通性

可达性不一定对称：u→v 不蕴含 v→u
「互相可达」才是等价关系
求 SCC 需要 Tarjan / Kosaraju
SCC 缩点后必为 DAG

⚡ 判定有向图是否强连通：正反两次 DFS

做法一（朴素）：从任意点 s 出发跑一次 DFS，若能访问全部 n 个点，说明 s 能到所有点；再把所有边反向，仍从 s 出发跑一次，若能访问全部点，说明所有点都能到 s。两次都成功 ⟺ 强连通。

为什么正确：第一次锁定「s 能到所有人」，第二次锁定「所有人能到 s」。结合起来，任意 u、v 都有 u → s → v，故两两可达。

做法二（高效）：直接跑 Tarjan 求 SCC，若 SCC 个数为 1 则强连通。虽然多写一点，但顺带得到了 SCC 划分。

复杂度：两种做法都是 O(n+m)。

🔑 判定技巧

正着走一遍、反着走一遍，两个方向都能走到所有人，才是强连通。

2点双连通与边双连通高频

双连通回答的是「这张图有多抗打」：把「删掉一个点」和「删掉一条边」分开考虑，就得到两把不同的尺子。

🛡️ 看图理解两类脆弱点

桥：唯一连接左右两片的边，删掉后连通块 +1。
割点：唯一的「中转枢纽」，删掉后左右两侧失联。
左边 5 个点构成的环没有割点，是点双连通的。
右边三角形同样点双连通，但与左边只靠两个点相连。

关键区别：一条边是不是桥，看它「是否在任何环上」；一个点是不是割点，看它「是否是某条路径的唯一必经点」。桥一定不在任何环上；割点则可能同时在多个环上。

概念	定义（删掉后连通块增加）	判定依据	典型性质
桥（割边）	删除边 e 后连通分量数 +1	e 不属于任何环	桥的两端点一定是割点（除非是叶子）
割点	删除点 u 后连通分量数 +1	存在两个子树无法绕过 u 互达	割点属于 ≥ 2 个点双分量
边双分量 e-BCC	不经过桥能互达的点集	去掉所有桥后的连通块	缩点后得到一棵树
点双分量 v-BCC	点双极大的子图（块）	栈中待弹的边构成一个块	一条边恰属于一个 v-BCC

✅ 边双连通（无桥）

任意两点间存在两条边不相交的路径。删任意一条边都不分裂。缩点后是一棵「桥树」。

⚠️ 点双连通（无割点）

任意两点间存在两条点不相交（除端点）的路径。删任意一个点都不分裂。一个点可属于多个块，块割树的节点是「块 + 割点」。

💡 为什么点双比边双「麻烦」？

边的归属唯一：一条边不可能同时属于两个不同的 v-BCC（否则两个块可以合并，违反「极大」）。所以「对边划分」很干净。

点的归属不唯一：一个割点可以同时属于多个 v-BCC。所以「对点划分」会重复计数，必须用「块割树」来表示。

实战建议：题目里若只需要「连通性/缩点」，优先用边双（简单、干净）；若涉及「必经点/删点后分裂」，才动用点双。

3三类分量对比辨析

维度	连通分量 (CC)	强连通分量 (SCC)	双连通分量 (BCC)
适用图	无向图	有向图	无向图
关系定义	u 与 v 有路径	u→v 且 v→u	u 与 v 有 2 条不交路径
划分对象	顶点	顶点	边双划边 / 点双划块
求法	一次 DFS/BFS	Tarjan / Kosaraju	Tarjan（low 判定）
缩点后	孤立点（无意义）	DAG	树（边双）
复杂度	O(n+m)	O(n+m)	O(n+m)

📐 三者的关系链

无向图：边双连通 ⟹ 点双连通 ⟹ 连通。抗打击能力从强到弱是边双 > 点双 > 连通。

有向图：强连通 ⟹ 弱连通（忽略方向后连通）。反之不成立（有向链 1→2→3 弱连通但不强连通）。

无向图可看成双向有向图：此时无向图的连通分量 = 有向图的强连通分量。所以很多 SCC 算法直接对无向图跑也得到正确结果。

4Tarjan 求 SCC 思想预览铺垫

Tarjan 用一个 DFS 同时维护两个数组：dfn[u]（u 是第几个被访问的）和 low[u]（从 u 的子树出发、经过至多一条非树边，能回溯到的最小 dfn）。

🕐

打时间戳

访问 u 时 dfn[u] = low[u] = ++timer，并把 u 压入栈。

🔍

递归邻居

对 v ∈ e[u]：若未访问，递归后 low[u] = min(low[u], low[v])。

↩️

回边更新

若 v 已访问且在栈中，low[u] = min(low[u], dfn[v])。

✂️

弹栈成团

若 dfn[u] == low[u]，把栈中元素弹到 u 为止，构成一个 SCC。

▶ dfn / low 更新过程演示

1从 1 号点出发：dfn[1] = low[1] = 1，1 入栈。

2走到 2：dfn[2] = low[2] = 2，2 入栈。栈内 [1, 2]。

3走到 3：dfn[3] = low[3] = 3，3 入栈。栈内 [1, 2, 3]。

43 有一条回边指向 1（1 已访问且在栈中）：low[3] = min(low[3], dfn[1]) = 1。

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

62 返回 1：low[1] = min(low[1], low[2]) = 1。此时 1 的 dfn == low，弹栈到 1，得到 SCC {1,2,3}。

核心判据：dfn[u] == low[u] 说明 u 是所在 SCC 的「最高点」，此时栈里从 u 往上的点都属于同一个 SCC。

C++Tarjan 求 SCC 核心框架（本讲只作预览，完整推导见 s5-15）

int dfn[MAXN], low[MAXN], timer, scc[MAXN], sccCnt;
int stk[MAXN], top; bool inStk[MAXN];

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u; inStk[u] = true;
    for (int v : e[u]) {
        if (!dfn[v]) {                    // 树边
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (inStk[v]) {           // 回边（v 在栈中才有效）
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {            // u 是所在 SCC 的根
        sccCnt++;
        int x;
        do { x = stk[top--]; inStk[x] = false; scc[x] = sccCnt; } while (x != u);
    }
}

dfn=1

low=1

↑入栈

回边↓

scc=1

弹栈

当前处理的单元

5边双缩点成树关键思想

把所有 e-BCC 各压缩成一个点，得到的图是一棵树（若原图连通）。原因很简单：e-BCC 之间只靠桥相连，而桥不可能成环，否则会被合并进同一个分量。

🌳 为什么缩点后一定是树

若缩点后有环，环上的边都不是桥，会被合进同一分量 → 矛盾。
树的边数 = 点数 − 1，正好等于「桥的数量」。
于是树上的距离、路径唯一、直径等问题都能直接套模板。

实战价值：题目一旦出现「删边后分裂」「必经边」，几乎都可以先边双缩点，把它变成树上问题。

🔑 缩点套路

边双缩点 → 得到一棵树 → 树上 DP / LCA / 树形计数，一路畅通。

案例案例1：判断有向图是否强连通经典

题目：给定 n 个点 m 条边的有向图，判断它是否为强连通图。n ≤ 10⁵，m ≤ 2×10⁵。

🔍 详细分析过程

第1步：定理 —— 有向图强连通 ⟺ 从任意点 s 出发正着能到达所有点，且反着也能到达所有点。

第2步：建反向图 —— 读入时同时把边 (u, v) 存到 g[u] 和 rg[v]。

第3步：两次 DFS —— 在 g 上从 1 出发统计可访问点数，在 rg 上重复一次。

第4步：陷阱 —— 反向图的建法是 rg[v].push_back(u)，不要写反，这是最常见的错误。

C++正反两次 DFS 判强连通 — 完整代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> g[MAXN], rg[MAXN];   // rg = 反向图
bool vis[MAXN];

int dfsCount(vector<int> adj[], int s, int n) {
    fill(vis + 1, vis + n + 1, false);
    int cnt = 0;
    stack<int> st; st.push(s); vis[s] = true;
    while (!st.empty()) {
        int u = st.top(); st.pop(); cnt++;
        for (int v : adj[u]) if (!vis[v]) { vis[v] = true; st.push(v); }
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);        // 正向
        rg[v].push_back(u);       // 反向：注意是 v → u
    }
    if (dfsCount(g, 1, n) == n && dfsCount(rg, 1, n) == n)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

运行结果

测试1（3 点 3 边成环）:
输入: 3 3 / 1 2 / 2 3 / 3 1
输出: Yes

测试2（3 点 2 边成链）:
输入: 3 2 / 1 2 / 2 3
输出: No     ← 反着走不到任何人

🔍 代码逐段解析 · 正反两次 DFS 判强连通

1g[] 与 rg[]（第 5~6 行）：正向图与反向图同时建。rg 存的是「谁指向 v」，即反向边。

2dfsCount(adj, s, n)：用显式栈写迭代 DFS，避免 10⁵ 规模爆系统栈；返回从 s 可访问的点数。

3fill(vis+1, vis+n+1, false)：每次调用前重置 vis，保证两次 DFS 互不污染。

4主循环：弹栈 u 时 cnt++，把未访问邻居压栈。注意 cnt 在弹出时统计而不是压入时，避免起点漏计。

5rg[v].push_back(u)：反向边的关键一行 —— 把 u 存到「终点 v」的表里。

6两次计数都 == n → Yes；任一不足 → No。

7易错点：① 反向图写反成 rg[u].push_back(v)，两次 DFS 等价于跑两遍正图，永远输出错误结论；② 复用 vis 却忘记清空。

复杂度 O(n+m)，n、m 达 1e5 规模也稳。

💡 为什么「两次 DFS」就能判定？

设从 s 出发正着能到集合 A，反着能到集合 B（也就是「能到达 s」的集合）。

若 A = B = V，则任意 u、v 都有 u → s → v，故两两可达，强连通。

反之若强连通，显然任意点都能到 s、s 也能到任意点，故 A = B = V。

注意：起点可以任选，因为强连通图的任意点都等价。

案例案例2：求所有桥 NOIP

题目：给定无向图，找出所有桥并按字典序输出。n ≤ 10⁵，m ≤ 2×10⁵，可能有重边。

🔍 详细分析过程

第1步：朴素做法 —— 枚举每条边删除，跑一次 DFS 判连通，O(m(n+m))，超时。

第2步：Tarjan 做法 —— DFS 中记录 dfn 与 low，对树边 (u, v)，若 low[v] > dfn[u]，说明 v 的子树无法绕过 u 回到更早的点，因此 (u, v) 是桥。

第3步：重边处理 —— 邻接表存边时同时存「边的编号 id」，DFS 时跳过「同一条边的反向边」而不是「同一个父节点」。这样才能正确处理重边。

C++Tarjan 求桥 — 完整代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct Edge { int to, id; };
vector<Edge> e[MAXN];
int dfn[MAXN], low[MAXN], timer;
vector<pair<int,int>> bridges;

void tarjan(int u, int fromId) {
    dfn[u] = low[u] = ++timer;
    for (auto [v, id] : e[u]) {
        if (id == fromId) continue;      // 跳过过来的那条边
        if (!dfn[v]) {
            tarjan(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u])            // v 回不到 u 或更早 → 桥
                bridges.push_back({min(u, v), max(u, v)});
        } else {
            low[u] = min(low[u], dfn[v]);   // 回边
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        e[u].push_back({v, i});
        e[v].push_back({u, i});      // 同一条无向边共享编号
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i]) tarjan(i, 0);
    sort(bridges.begin(), bridges.end());
    for (auto &b : bridges) cout << b.first << " " << b.second << endl;
    return 0;
}

运行结果

输入: 5 5
      1 2
      2 3
      3 1
      3 4
      4 5
输出: 3 4
      4 5
（1-2-3 构成环无桥；3-4 和 4-5 都是桥）

🔍 代码逐段解析 · Tarjan 求桥

1struct Edge { to, id }：邻接表存「目标点 + 边编号」，同一条无向边的两个方向共享同一个 id —— 重边正确性的根基。

2tarjan(u, fromId)：进入 u 时打时间戳 dfn[u] = low[u] = ++timer。

3if (id == fromId) continue：只跳过「走过来那条边」本身；编号不同的重边不会被误跳。

4树边分支：递归 v 后用 low[v] 更新 low[u]；若 low[v] > dfn[u]，v 的子树回不到 u 或更早 → (u,v) 是桥，按「小号在前」存入 bridges。

5回边分支：v 已访问，用 dfn[v]（不是 low[v]！）更新 low[u]。

6main 中外层枚举起点：if (!dfn[i]) tarjan(i, 0) 处理非连通图；最后 sort 保证按字典序输出。

7易错点：① 回边更新写成 low[v]，会把桥误判成环边；② 用 v == fa 跳过，重边场景翻车。

一次 DFS O(n+m) 完成，比「逐边删除 + DFS」的 O(m(n+m)) 快几个数量级。

💡 重边为什么必须用「边编号」而不是「父节点」跳过？

假设有两条重边 (1, 2) 和 (1, 2)。如果只记「父节点 1」，从 2 出发看到邻居 1 时会以为这是父亲而跳过，导致 low[2] 无法更新，从而把这两条重边误判为桥。

换成记录「来的那条边的编号」，第二条重边编号不同就不会被跳过，low 能正确回溯，判定为「不是桥」——这才是正确答案。

案例案例3：边双连通分量划分进阶

题目：给定无向图，求所有边双连通分量，输出每个分量包含的顶点。n ≤ 10⁵，m ≤ 2×10⁵。

🔍 详细分析过程

思路一（先找桥再 DFS）推荐 —— 先用 Tarjan 求出所有桥并标记；再对全图做一次 DFS，遇到桥就不走，每次 DFS 覆盖的点集就是一个 e-BCC。思路直白，代码量小。

思路二（Tarjan 边栈）进阶 —— DFS 时把边压栈，当 low[v] > dfn[u] 时弹出到 (u, v) 为止，栈里这些边构成一个 e-BCC。能同时处理点双，但代码更绕。

选型建议：只需 e-BCC 时用思路一，需要 v-BCC / 割点时用思路二。

C++边双连通分量划分 — 完整代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct Edge { int to, id; };
vector<Edge> e[MAXN];
int dfn[MAXN], low[MAXN], timer;
bool isBridge[MAXN];          // 按边编号标记
int comp[MAXN];               // 每个点所属的 e-BCC 编号

void tarjan(int u, int fromId) {
    dfn[u] = low[u] = ++timer;
    for (auto [v, id] : e[u]) {
        if (id == fromId) continue;
        if (!dfn[v]) {
            tarjan(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) isBridge[id] = true;
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void dfsComp(int u, int c) {
    comp[u] = c;
    for (auto [v, id] : e[u]) {
        if (isBridge[id] || comp[v]) continue;   // 不走桥
        dfsComp(v, c);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        e[u].push_back({v, i}); e[v].push_back({u, i});
    }
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, 0);
    int cnt = 0;
    for (int i = 1; i <= n; i++) if (!comp[i]) dfsComp(i, ++cnt);
    cout << "分量数: " << cnt << endl;
    for (int i = 1; i <= n; i++) cout << i << " -> 分量 " << comp[i] << endl;
    return 0;
}

运行结果

输入: 6 6
      1 2 / 2 3 / 3 1      (三角形)
      3 4                  (桥)
      4 5 / 5 6 / 6 4      (三角形)
输出:
分量数: 2
1 -> 分量 1
2 -> 分量 1
3 -> 分量 1
4 -> 分量 2
5 -> 分量 2
6 -> 分量 2

🔍 代码逐段解析 · 边双连通分量划分

第一段：tarjan（第 8~18 行） —— 与求桥几乎同款：树边更新 low、low[v] > dfn[u] 时把边编号标记进 isBridge[id]。注意这里标记的是「边的编号」而不是点，因为桥属于边。

第二段：dfsComp（第 20~25 行） —— 在「删掉所有桥」的图上 DFS：遇到 isBridge 的边直接 continue，遇到已分配 comp 的点也 continue。每次从新点启动就得到一个新 e-BCC。

第三段：main（第 27~40 行） —— 先对所有未访问点跑 tarjan，再对未分配 comp 的点跑 dfsComp(i, ++cnt)，最后输出分量数与每个点的归属。

易错点 —— ① dfsComp 忘记判 comp[v] 会在重边/环上反复递归甚至死循环；② isBridge 按边编号标记时数组要开到 2×10⁵ 而不是点数。

模块 03

实践应用

三道完整题目，从识别连通性模型到写出可提交代码。

题1校园网络连通性检查

题 1割点判定

n 台服务器、m 条双向链路。求网络被分成了几个互联区域；若只有 1 个区域，再判断是否是「无单点故障网络」（即不存在割点）。

输入格式：第一行 n, m（1 ≤ n ≤ 10⁵，0 ≤ m ≤ 2×10⁵）。接下来 m 行每行 u, v。

输出格式：第一行输出区域数 k；若 k == 1，第二行输出 Yes（无割点）或 No（有割点）。

输入样例：

输入

输出样例：

输出

1
No

数据范围：1s / 256MB。

🔍 题目分析

方法一（暴力删点）会超时 —— 枚举每个点删除后再跑 DFS 判连通，O(n(n+m))，n = 10⁵ 时不可行。

方法二（Tarjan 求割点）正解 —— 一次 DFS 求割点，O(n+m)。割点判定规则：

· 若 u 是 DFS 树的根，且它有 ≥ 2 个儿子，则 u 是割点；

· 若 u 不是根，且存在儿子 v 使 low[v] >= dfn[u]，则 u 是割点。

C++割点判定 — 完整代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> e[MAXN];
int dfn[MAXN], low[MAXN], timer;
bool cut[MAXN];

void tarjan(int u, int root) {
    dfn[u] = low[u] = ++timer;
    int child = 0;
    for (int v : e[u]) {
        if (!dfn[v]) {
            child++;
            tarjan(v, root);
            low[u] = min(low[u], low[v]);
            if (u != root && low[v] >= dfn[u]) cut[u] = true;
            if (u == root && child >= 2) cut[u] = true;
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int cc[MAXN];
void dfsCC(int u, int c) {
    cc[u] = c;
    for (int v : e[u]) if (!cc[v]) dfsCC(v, c);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); }
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i, i);
    int k = 0;
    for (int i = 1; i <= n; i++) if (!cc[i]) dfsCC(i, ++k);
    cout << k << endl;
    if (k == 1) {
        bool has = false;
        for (int i = 1; i <= n; i++) if (cut[i]) has = true;
        cout << (has ? "No" : "Yes") << endl;
    }
    return 0;
}

运行结果

输入: 4 4 / 1 2 / 2 3 / 3 1 / 3 4
输出: 1
      No          （3 号是割点，删掉后 4 号孤立）

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

1tarjan(u, root)：root 记录当前 DFS 树的根，因为根与非根的割点判据不同。

2int child = 0：统计 u 在 DFS 树中的「儿子数」（只数树边分支里的 child++）。

3非根判定：u != root && low[v] >= dfn[u] —— v 的子树绕不回 u 及更早的点，删 u 必分裂。

4根判定：u == root && child >= 2 —— 根的两个子树之间除根外无路可通。

5回边分支：low[u] = min(low[u], dfn[v])，用 dfn[v] 而非 low[v]。

6dfsCC 数连通块：先输出区域数 k；仅当 k==1 时才输出是否存在割点（割点判定只在连通块内部有意义）。

7易错点：① 桥用 > 而割点用 ≥，等号丢掉就全错；② 根的 child 只在「树边分支」里自增，别把回边也算进去。

样例中 3 号点：low[4] = dfn[4] ≥ dfn[3]，且 3 非根 → 3 是割点，输出 No。

💡 易错提示

割点条件里 low[v] >= dfn[u] 用的是 >=，而桥条件用的是 >。差一个等号，语义完全不同：割点允许「v 能绕回 u 本身」，因为删掉 u 后 v 依然会失去 u。

题2关键链路（桥与网络加固）

题 2桥的应用

n 个点 m 条边的无向连通图。若删掉某条边网络会分裂，这条边称为「关键链路」。求关键链路的数量并输出。

输入格式：第一行 n, m（2 ≤ n ≤ 10⁵，1 ≤ m ≤ 2×10⁵）。接下来 m 行每行 u, v，保证图连通，允许重边。

输出格式：第一行一个整数 k；接下来 k 行每行两个整数（升序），按第一个数升序输出。

输入样例：

输入

输出样例：

输出

2
3 4
4 5

数据范围：1s / 256MB。

🔍 题目分析

方法一（枚举删除）O(m(n+m)) —— 逐条边删掉跑 DFS，简单但超时。

方法二（Tarjan 求桥）正解 —— 一次 DFS 求桥，O(n+m)。注意用边编号跳过反向边，正确处理重边。

结论：关键链路 = 桥。此题与案例 2 是同一模型的不同包装。

C++关键链路（桥）— 完整代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
struct Edge { int to, id; };
vector<Edge> e[MAXN];
int dfn[MAXN], low[MAXN], timer;
vector<pair<int,int>> ans;

void tarjan(int u, int fromId) {
    dfn[u] = low[u] = ++timer;
    for (auto [v, id] : e[u]) {
        if (id == fromId) continue;
        if (!dfn[v]) {
            tarjan(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) ans.push_back({min(u,v), max(u,v)});
        } else low[u] = min(low[u], dfn[v]);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        e[u].push_back({v, i}); e[v].push_back({u, i});
    }
    tarjan(1, 0);
    sort(ans.begin(), ans.end());
    cout << ans.size() << endl;
    for (auto &p : ans) cout << p.first << " " << p.second << endl;
    return 0;
}

运行结果

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

🔍 代码逐段解析 · 关键链路（求桥计数）

第 5~7 行 —— 结构体邻接表，每条边两个方向共享编号 id，为重边正确性做准备。

第 9~18 行 —— tarjan 主体：树边递归后判 low[v] > dfn[u]，成立则把 {min(u,v), max(u,v)} 压入答案；回边只更新 low。

第 20~31 行 —— main：读边建图后调用 tarjan(1, 0)（本题保证连通，只跑一次），sort 后先输出桥数再逐行输出桥的两端点。

易错点 —— ① 输出前必须 sort，DFS 发现桥的顺序是按时间戳而非字典序；② 无重边时也可用父节点法，但本题允许重边，必须用边编号。

题3缩点后统计入度为零的分量

题 3SCC · 缩点

给定有向图，求 SCC 个数，并统计缩点后入度为 0 的分量中有多少个原始顶点。

输入格式：第一行 n, m（1 ≤ n ≤ 10⁵，0 ≤ m ≤ 2×10⁵）。接下来 m 行每行 u, v。

输出格式：第一行 SCC 个数；第二行入度为 0 的分量中的原始顶点数。

输入样例：

输入

输出样例：

输出

4
2

数据范围：1s / 256MB。

🔍 题目分析

样例解释：SCC 为 {1,2}、{3}、{4}、{5}，共 4 个。缩点后是 1→3→4→5 的链，只有 {1,2} 入度为 0，贡献 2 个原始顶点。

方法一（Kosaraju）易懂 —— 正图 DFS 记录结束时间，按结束时间倒序在反图上 DFS，每次覆盖的集合是一个 SCC。O(n+m)。

方法二（Tarjan）更常用 —— 一次 DFS 完成，常数更小。推荐作为模板记忆。

关键细节：统计入度时要忽略「同一个 SCC 内部」的边，否则会误判。

C++SCC 缩点统计 — Tarjan 版完整代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> e[MAXN];
int dfn[MAXN], low[MAXN], timer;
int stk[MAXN], top, sccOf[MAXN], sccCnt, sz[MAXN];
bool inStk[MAXN];

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u; inStk[u] = true;
    for (int v : e[u]) {
        if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); }
        else if (inStk[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u]) {
        sccCnt++; int x;
        do { x = stk[top--]; inStk[x] = false; sccOf[x] = sccCnt; sz[sccCnt]++; } while (x != u);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    for (int i = 1; i <= m; i++) { int u, v; cin >> u >> v; e[u].push_back(v); }
    for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);
    cout << sccCnt << endl;
    vector<int> indeg(sccCnt + 1, 0);
    for (int u = 1; u <= n; u++)
        for (int v : e[u])
            if (sccOf[u] != sccOf[v]) indeg[sccOf[v]]++;    // 只算跨分量边
    int res = 0;
    for (int c = 1; c <= sccCnt; c++) if (indeg[c] == 0) res += sz[c];
    cout << res << endl;
    return 0;
}

运行结果

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

🔍 代码逐段解析 · SCC 缩点统计

1tarjan 入口：dfn[u] = low[u] = ++timer，u 入栈并标 inStk —— 栈里始终是「还未归入任何 SCC 的点」。

2树边 / 回边：未访问递归后取 low[v]；已访问且在栈中取 dfn[v]。

3dfn[u] == low[u]：u 是其 SCC 的根，do-while 弹栈直到弹出 u，弹出的每个点 sccOf 记为同一编号，sz 计数。

4统计跨分量边：双重循环扫所有边，仅当 sccOf[u] != sccOf[v] 时 indeg[sccOf[v]]++ —— 过滤内部边是正确性关键。

5汇总答案：所有入度为 0 的分量，把它们的 sz 累加输出。

6易错点：① 忘记 inStk 过滤，回边会错误更新 low；② 枚举边统计入度时用 sccOf[v] 而不是 sccOf[u]（入度加给「到达的分量」）。

样例：SCC 为 {1,2}{3}{4}{5} 共 4 个；缩点后链 {1,2}→{3}→{4}→{5}，仅 {1,2} 入度为 0，含 2 个原始顶点。

模块 04

总结提升

①核心要点与万能模板

概念	判定依据	缩点后	典型用途
连通分量 CC	一次 DFS 的外层启动次数	孤立点	连通性检查
强连通分量 SCC	dfn[u] == low[u] 弹栈	DAG	环上 DP、拓扑排序
桥	树边 (u,v) 满足 low[v] > dfn[u]	—	关键边、网络脆弱点
割点	非根 low[v] >= dfn[u]；根有 ≥ 2 子	—	必经点、删点分裂
边双 e-BCC	去掉所有桥后的连通块	树	树上距离、树上 DP
点双 v-BCC	边栈弹到 (u,v) 为止	块割树	必经点路径计数

万能模板：Tarjan 一函数通吃（SCC / 割点 / 桥）

C++Tarjan 通用框架

int dfn[MAXN], low[MAXN], timer;
int stk[MAXN], top; bool inStk[MAXN];
int sccOf[MAXN], sccCnt;

void tarjan(int u, int fromId, int root) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u; inStk[u] = true;
    int child = 0;
    for (auto [v, id] : e[u]) {
        if (id == fromId) continue;        // 无向图跳反向边
        if (!dfn[v]) {
            child++;
            tarjan(v, id, root);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) { /* 桥 */ }
            if (u != root && low[v] >= dfn[u]) { /* 割点 */ }
            if (u == root && child >= 2) { /* 根是割点 */ }
        } else if (inStk[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }
    if (dfn[u] == low[u]) {              // SCC 弹栈
        sccCnt++; int x;
        do { x = stk[top--]; inStk[x] = false; sccOf[x] = sccCnt; } while (x != u);
    }
}

②拓展案例

拓展1：Kosaraju 求 SCC（两次 DFS 版）

💡 思路：第一次在正图上 DFS，记录每个点的「结束时间」（回溯时入栈）。第二次按结束时间从晚到早的顺序，在反图上 DFS，每次覆盖的点集就是一个 SCC。

为什么正确：结束时间最晚的点必属于「源 SCC」（缩点后入度为 0 的分量）；在反图上从它出发能走到的点，恰好是正图上能走到它的点，交集即该 SCC。

C++Kosaraju 算法

vector<int> g[MAXN], rg[MAXN];
bool vis[MAXN];
int order[MAXN], cnt, sccOf[MAXN];

void dfs1(int u) {
    vis[u] = true;
    for (int v : g[u]) if (!vis[v]) dfs1(v);
    order[++cnt] = u;                 // 后序：结束时间递增
}
void dfs2(int u, int c) {
    sccOf[u] = c;
    for (int v : rg[u]) if (!sccOf[v]) dfs2(v, c);
}
// 主函数：dfs1 全部点 → 逆序 order，在反图上 dfs2

运行结果

输入: 5 5 / 1 2 / 2 1 / 2 3 / 3 4 / 4 5
输出: 4 个 SCC（{1,2}{3}{4}{5}）

拓展2：点双分量与块割树

💡 思路：DFS 时把「走过的边」压栈（存边不存点）。当 low[v] >= dfn[u] 成立时，从栈顶弹出边直到弹出 (u, v) 为止，这些边构成一个点双分量。

块割树的构造：新建「块节点」与「割点节点」，每个块向它包含的所有割点连边。得到的树有 B + C 个节点，其中 B 是块数、C 是割点数。

C++点双分量（边栈版）

struct E { int from, to; };
vector<E> estk;
vector<int> bcc[MAXN]; int bccCnt;

void tarjan(int u, int fromId) {
    dfn[u] = low[u] = ++timer;
    for (auto [v, id] : e[u]) {
        if (id == fromId) continue;
        if (!dfn[v]) {
            estk.push_back({u, v});
            tarjan(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) {        // u 是割点（或根）→ 弹出一个块
                bccCnt++;
                while (true) {
                    E x = estk.back(); estk.pop_back();
                    bcc[bccCnt].push_back(x.from);
                    bcc[bccCnt].push_back(x.to);
                    if (x.from == u && x.to == v) break;
                }
            }
        } else if (dfn[v] < dfn[u]) {
            estk.push_back({u, v});      // 只压「向下」的回边
            low[u] = min(low[u], dfn[v]);
        }
    }
}

运行结果

输入: 5 5 / 1 2 / 2 3 / 3 1 / 3 4 / 4 5
输出: 块1 = {1,2,3}，块2 = {3,4}
（3 是割点，同时属于两个块）

拓展3：受欢迎的牛（缩点 + 出度统计）

💡 经典结论：有向图中「能被所有人到达」的点必须全部位于同一个 SCC。缩点成 DAG 后，这样的 SCC 必须出度为 0 且唯一。

为什么唯一：若有 ≥ 2 个出度为 0 的 SCC，它们互相到不了，都无法被对方到达 → 无解。

C++缩点后统计唯一零出度分量

// 求出 sccOf[]、sccCnt、sz[] 后：
vector<int> outdeg(sccCnt + 1, 0);
for (int u = 1; u <= n; u++)
    for (int v : e[u])
        if (sccOf[u] != sccOf[v]) outdeg[sccOf[u]]++;
int zeros = 0, which = -1;
for (int c = 1; c <= sccCnt; c++)
    if (outdeg[c] == 0) { zeros++; which = c; }
if (zeros != 1) cout << 0 << endl;
else cout << sz[which] << endl;

运行结果

输入: 4 4 / 1 2 / 2 1 / 2 3 / 3 4
缩点后：{1,2} → {3} → {4}
outdeg[{1,2}]=1, outdeg[{3}]=1, outdeg[{4}]=0
输出: 1      ← 只有 {4} 出度为 0，大小 1

③思考与启发

思考1：为什么「强连通分量」缩点后一定是 DAG？

查看参考解答

反证：若缩点后存在有向环 C₁ → C₂ → … → Cₖ → C₁，那么这些分量之间两两互为可达（绕环一圈即可），于是它们的并集满足「任意两点互相可达」，应该被合并成同一个 SCC，与「SCC 是极大的」矛盾。

所以缩点后的图无环，即 DAG。「SCC 极大性」正是这条结论的保证。

思考2：为什么桥的判定是 low[v] > dfn[u]，而割点是 low[v] >= dfn[u]？

查看参考解答

桥的情形：删掉边 (u, v) 后，若 v 的子树还能绕回 u 本身（low[v] == dfn[u]），说明存在另一条从 v 的子树到 u 的路径，那么 (u, v) 与那条路径构成环，删掉它不影响连通 → 不是桥。所以必须 low[v] > dfn[u]（严格大于）。

割点的情形：删掉点 u 后，v 的子树不仅失去边 (u, v)，还失去了 u 本身。即使 low[v] == dfn[u]，删掉 u 后 v 的子树也无法通过 u 到达 u 的其他子树 → u 依然是割点。所以条件是 low[v] >= dfn[u]。

一句话记忆：删边看「能否绕回来」，删点看「绕回也没用」。

思考3：为什么边双缩点后是树，点双缩点后却是「块割树」？

查看参考解答

边双：划分的对象是边，一条边恰属于一个 e-BCC，分量之间只剩桥。桥不可能构成环（否则环上的边都不是桥），所以缩点后是无环连通图 = 树。

点双：划分的对象是点，而一个割点可以属于多个块。所以「点」无法被唯一划分到某个块里，必须把「块」和「割点」都作为节点，才能表达完整的邻接关系 —— 这就是块割树。

❌ 错误

n = 10⁵ 的链式图直接递归 Tarjan，系统栈溢出导致 RE。

✅ 正确

编译选项加 -Wl,--stack=268435456 扩栈，或改写为迭代版 Tarjan / 先做重编号减小深度。

口诀：十万递归会爆栈，栈空间要提前扩！

📋速查表

目标	判据	注意
连通分量数	DFS 外层启动次数	孤立点自己算一块
是否强连通	正反两次 DFS 均达全部点	反向图建法 `rg[v].push_back(u)`
SCC 划分	dfn[u] == low[u] 时弹栈	只有 inStk[v] 才用 dfn[v] 更新 low
桥	low[v] > dfn[u]（树边）	重边要用边编号
割点	非根 low[v] >= dfn[u]；根 child ≥ 2	等号不能丢
边双分量	删掉所有桥后的连通块	缩点后是树
点双分量	low[v] >= dfn[u] 时弹边栈	割点属于多个块

📌笔记卡

必记概念

SCC 缩点 → DAG
边双缩点 → 树
桥：low[v] > dfn[u]
割点：low[v] >= dfn[u] 或根 child ≥ 2

必背模板

Tarjan 求 SCC（栈 + dfn/low）
Tarjan 求桥 / 割点
Kosaraju（两次 DFS）
边双划分（先求桥再 DFS）

考场提醒

重边必须用边编号
割点等号不能少
缩点统计要过滤内部边
10⁵ 递归记得开大栈

课后练习

分层练习作业

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

🟢 A组 · 基础（4题）

A1概念题

判断：① 强连通图一定弱连通；② 无桥的图一定无割点；③ 桥的两个端点一定是割点。

查看参考答案

① 正确。强连通要求任意两点互相可达，自然忽略方向后也连通。

② 错误。反例：两个三角形共享一个顶点（沙漏形），没有桥，但共享的顶点是割点。

③ 错误。反例：一条边 (1, 2) 且 2 是叶子（度数为 1），边是桥，但删掉 2 后图只剩 1，连通块数没增加，2 不是割点。

A2编程题

统计无向图的连通分量个数。

查看参考答案

#include <bits/stdc++.h>
using namespace std;
vector<int> e[100005]; bool vis[100005];
void dfs(int u) { vis[u] = 1; for (int v : e[u]) if (!vis[v]) dfs(v); }
int main() {
    int n, m, c = 0; cin >> n >> m;
    for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; e[u].push_back(v); e[v].push_back(u); }
    for (int i = 1; i <= n; i++) if (!vis[i]) { c++; dfs(i); }
    cout << c;
}

逐段解析：第 3 行建邻接表与 vis；第 4 行递归 DFS 标记整个连通块；第 6~7 行外层枚举 1..n，遇到未访问点就把计数 c 加一并启动一次 DFS；第 8 行输出 c。易错：计数必须在「启动 DFS」时加一，而不是在 DFS 内部加；n = 10⁵ 时链式图递归会爆栈，建议加 -Wl,--stack=268435456 或改 BFS。

A3编程题

判断有向图是否为强连通图。

查看参考答案

// 正图 dfs 一次、反图 dfs 一次，两次都访问到 n 个点即为强连通
int cnt1 = dfsCount(g,  1, n);
int cnt2 = dfsCount(rg, 1, n);
cout << ((cnt1 == n && cnt2 == n) ? "Yes" : "No");

思路：「正着能到所有人」+「所有人都能到起点」= 任意两点经起点互达。

易错：反向图建错（写成 rg[u].push_back(v)）；或只跑一次 DFS 就下结论。

A4选择题

一棵有 n 个节点的树（n ≥ 2），它有（）个桥。A. 0 B. 1 C. n−1 D. n

查看参考答案

答案：C。树无环，每条边都不在任何环上，删掉任意一条边都会使树分成两棵子树，连通块数 +1，所以所有 n−1 条边都是桥。

推论：树的所有非叶节点都是割点（叶子不是）。

易错：认为树太「简单」所以没有桥 —— 恰好相反，树是最「脆弱」的连通图。

🟡 B组 · 提高（4题）

B1Tarjan

求无向图的所有桥并输出（允许重边）。

查看参考答案

思路：DFS 求 dfn/low，树边满足 low[v] > dfn[u] 即为桥。

struct Edge { int to, id; };
void tarjan(int u, int fromId) {
    dfn[u] = low[u] = ++timer;
    for (auto [v, id] : e[u]) {
        if (id == fromId) continue;
        if (!dfn[v]) {
            tarjan(v, id);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) bridge.push_back({min(u,v), max(u,v)});
        } else low[u] = min(low[u], dfn[v]);
    }
}

易错：用 v == fa 跳过导致重边误判；或桥只记录一次却输出两遍。

B2SCC 缩点

给定有向图，求 SCC 个数与最大 SCC 的大小。

查看参考答案

思路：Tarjan 弹栈时统计每个 SCC 的点数，取最大值。

if (dfn[u] == low[u]) {
    sccCnt++; int x, s = 0;
    do { x = stk[top--]; inStk[x] = false; s++; } while (x != u);
    mx = max(mx, s);
}

易错：忘记 inStk[x] = false，导致后续 low 更新用到已出栈的点；或计数器在循环外初始化。

B3割点应用

给定无向连通图，删掉一个点后最多能使图分成几个连通块？

查看参考答案

思路：对非根节点 u，删掉它能增加的连通块数 = 满足 low[v] >= dfn[u] 的儿子 v 的个数。对根节点，增加数 = 儿子数 − 1。

void tarjan(int u, int root) {
    dfn[u] = low[u] = ++timer;
    int child = 0, cutCnt = 0;
    for (int v : e[u]) {
        if (!dfn[v]) {
            child++;
            tarjan(v, root);
            low[u] = min(low[u], low[v]);
            if (low[v] >= dfn[u]) cutCnt++;
        } else low[u] = min(low[u], dfn[v]);
    }
    if (u == root) cutCnt = child - 1;   // 根的特判
    ans = max(ans, cutCnt + 1);                // 至少还有自己那一块
}

易错：根没有特判；或忘记加 1（自己保留的那块）。

B4边双缩点

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

查看参考答案

关键结论：缩点后树的边数 = 原图中桥的数量。

理由：缩点后每条边恰好对应原图中的一座桥；而树有 e = V − 1，V = 分量数，所以 e = 分量数 − 1 = 桥数。

做法：Tarjan 求桥 → 不走桥 DFS 划分量 → 输出桥的数量（或直接输出分量数 − 1）。

易错：把「桥数」和「分量数」搞混。

🔴 C组 · 挑战（4题）

C1综合

有向图中，至少需要加多少条边才能把整个图变成一个强连通图？（图保证弱连通）

查看参考答案

思路：SCC 缩点成 DAG 后，设 A = 入度为 0 的分量数，B = 出度为 0 的分量数。

结论：若缩点后只有一个点（原图已强连通），答案是 0；否则答案是 max(A, B)。

// 缩点后统计
int A = 0, B = 0;
for (int c = 1; c <= sccCnt; c++) {
    if (indeg[c] == 0) A++;
    if (outdeg[c] == 0) B++;
}
if (sccCnt == 1) cout << 0;
else cout << max(A, B);

直观理解：加一条边最多消灭一个零入度和一个零出度分量，所以至少 max(A,B) 条；构造上可证明 max(A,B) 条总是够用（把零出度连到零入度，首尾接成一个大环）。

易错：漏掉「已强连通返回 0」的特判，此时 A = B = 1，会错误输出 1。

C2困难

给定无向连通图，每条边有一个破坏代价。求最小的「割」——删掉一组边使图分裂，且总代价最小。（全局最小割）

查看参考答案

方法一（Stoer-Wagner）正解：不断用「最大邻接搜索」找出一对点 s、t，记录当前割的大小，然后把 s 与 t 合并，重复 n − 1 次。复杂度 O(n³)，n ≤ 500 时可行。

方法二（枚举源汇 + 最大流）：固定点 1，枚举另一个点 t，跑最大流求最小割，取最小值。复杂度 O(n · MaxFlow)，n 稍大就超时。

// Stoer-Wagner 核心：最大邻接搜索
for (int phase = n; phase > 1; phase--) {
    vector<long long> w(n + 1, 0);
    vector<bool> in(n + 1, false);
    int s = 0, t = 0;
    for (int i = 1; i <= phase; i++) {
        int mx = -1;
        for (int j = 1; j <= n; j++)
            if (alive[j] && !in[j] && (mx == -1 || w[j] > w[mx])) mx = j;
        in[mx] = true; s = t; t = mx;
        for (int j = 1; j <= n; j++)
            if (alive[j] && !in[j]) w[j] += g[mx][j];
    }
    best = min(best, w[t]);
    for (int j = 1; j <= n; j++)
        if (alive[j]) { g[s][j] += g[t][j]; g[j][s] += g[j][t]; }
    alive[t] = false;
}

易错：把「最小割」当成「最小桥」（最小桥只是割大小为 1 的特例）；或忘记合并后清除点 t。

C3树上综合

边双缩点后得到一棵树，树上有 q 次询问「两点间路径上的最小边权」。请设计做法。

查看参考答案

思路：先边双缩点建树（缩点后边权取该桥的权），再用 LCA + 倍增维护「向上 2^k 步的最小边权」。

// up[k][u] = u 的 2^k 级祖先；mn[k][u] = 向上 2^k 步内的最小边权
for (int k = 1; k < LOG; k++)
  for (int u = 1; u <= N; u++) {
      up[k][u] = up[k-1][ up[k-1][u] ];
      mn[k][u] = min(mn[k-1][u], mn[k-1][ up[k-1][u] ]);
  }
// 查询：把 u、v 提到同深度时边跳边取 min，再同步上跳取 min

复杂度：预处理 O(N log N)，每次询问 O(log N)。

易错：缩点后忘了把树上的点重新编号；或 mn 数组初值设为 0（应设为 INF）。

C4初赛真题风格

一个有 n 个顶点的无向简单图，若删掉任意一条边连通块数都不变，则它至少有多少条边？

查看参考答案

分析：「删掉任意一条边连通块数都不变」等价于没有桥，即图是边双连通的。

下界构造：若图连通且没有桥，则每条边都在某个环上。最少边的无桥连通图是「一个简单环」，此时 m = n（n ≥ 3）。

若允许不连通，则每个连通分量都必须是环，最少边数 = n（n ≥ 3 且每个分量长度 ≥ 3）。

答案：在连通的简单图前提下，最少 m = n（一个 n 元环）。

易错：误答 n − 1（那是树，全是桥）；或忽略 n ≥ 3 的限制（n = 2 时两点间只能有一条边，必是桥）。

🏆 洛谷原题精选（12道）

以下 12 道题覆盖连通性判定、Tarjan 求 SCC、割点与桥、边双缩点以及缩点后的 DAG 统计，按难度从低到高排列。

P1656
炸铁路（求桥模板）提高

P2863
[USACO06JAN] The Cow Prom S提高

P2002
消息扩散（SCC 缩点）提高

P2341
[USACO03FALL/HAOI2006] 受欢迎的牛 G提高

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

P2812
校园网络（SCC 缩点 + 入出度）提高

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

P2746
[USACO5.3] 校园网 Network of Schools提高

P1262
间谍网络（SCC + 贪心）提高

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

P3469
[POI2008] BLO-Blockade（割点计数）提高

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

情景导航

城市道路 = 无向连通

单行道 = 有向强连通

独木桥 = 桥

唯一中转站 = 割点

知识探究

🔗 无向图连通性

🚦 有向图强连通性

🛡️ 看图理解两类脆弱点

✅ 边双连通（无桥）

⚠️ 点双连通（无割点）

💡 为什么点双比边双「麻烦」？

打时间戳

递归邻居

回边更新

弹栈成团

🌳 为什么缩点后一定是树

💡 为什么「两次 DFS」就能判定？

💡 重边为什么必须用「边编号」而不是「父节点」跳过？

实践应用

n 台服务器、m 条双向链路。求网络被分成了几个互联区域；若只有 1 个区域，再判断是否是「无单点故障网络」（即不存在割点）。

💡 易错提示

n 个点 m 条边的无向连通图。若删掉某条边网络会分裂，这条边称为「关键链路」。求关键链路的数量并输出。

给定有向图，求 SCC 个数，并统计缩点后入度为 0 的分量中有多少个原始顶点。

总结提升

学习检测

重边图用「父节点」跳过反向边

割点判定漏了根的特殊情况

缩点统计入度时把内部边也算上

把「弱连通」当成「强连通」

递归深度爆栈

必记概念

必背模板

考场提醒

分层练习作业

🟢 A组 · 基础（4题）

判断：① 强连通图一定弱连通；② 无桥的图一定无割点；③ 桥的两个端点一定是割点。

统计无向图的连通分量个数。

判断有向图是否为强连通图。

一棵有 n 个节点的树（n ≥ 2），它有（ ）个桥。A. 0 B. 1 C. n−1 D. n

🟡 B组 · 提高（4题）

求无向图的所有桥并输出（允许重边）。

给定有向图，求 SCC 个数与最大 SCC 的大小。

给定无向连通图，删掉一个点后最多能使图分成几个连通块？

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

🔴 C组 · 挑战（4题）

有向图中，至少需要加多少条边才能把整个图变成一个强连通图？（图保证弱连通）

给定无向连通图，每条边有一个破坏代价。求最小的「割」——删掉一组边使图分裂，且总代价最小。（全局最小割）

边双缩点后得到一棵树，树上有 q 次询问「两点间路径上的最小边权」。请设计做法。

一个有 n 个顶点的无向简单图，若删掉任意一条边连通块数都不变，则它至少有多少条边？

🏆 洛谷原题精选（12道）

一棵有 n 个节点的树（n ≥ 2），它有（）个桥。A. 0 B. 1 C. n−1 D. n