第十二章图论进阶¶

图论是竞赛中的重灾区，也是区分铜银金的关键。本章覆盖强连通分量、割点与桥、二分图、网络流、树上高级技巧等核心内容，每一节均给出原理图解、竞赛风格代码与复杂度分析。

12.1 强连通分量（SCC）¶

12.1.1 问题引入¶

对于一张有向图，若从顶点 \(u\) 出发能到达 \(v\)，同时从 \(v\) 也能到达 \(u\)，则称 \(u, v\) 强连通。极大强连通子图称为强连通分量（Strongly Connected Component, SCC）。

缩点后得到一张 DAG（有环→无环），是许多图论问题的第一步。

12.1.2 Tarjan 算法原理¶

Tarjan 算法一次 DFS 搞定，核心是维护两个数组：

dfn[u]：节点 \(u\) 的 DFS 序时间戳（第几个被访问）
low[u]：从 \(u\) 出发，经过子树和至多一条反向边，能到达的最小 dfn 值

关键判定：若 low[u] == dfn[u]，则 \(u\) 是当前 SCC 在栈中的根，栈中从 \(u\) 到栈顶的所有节点构成一个 SCC。

flowchart TD
    subgraph Tarjan DFS
        A["访问 u，记录 dfn[u]，入栈"] --> B["遍历 u 的邻接点 v"]
        B --> C{v 是否访问过?}
        C -- 否 --> D["递归访问 v，更新 low[u] = min(low[u], low[v])"]
        C -- 是且 v 在栈中 --> E["low[u] = min(low[u], dfn[v])"]
        D --> F{"low[u] == dfn[u]?"}
        E --> F
        F -- 是 --> G["弹出栈顶直到 u，形成一个 SCC"]
        F -- 否 --> H["返回上层"]
        G --> H
    end

12.1.3 图解¶

有向图示例：
  1 → 2 → 3 → 1    (SCC1: {1, 2, 3})
  3 → 4 → 5 → 4    (SCC2: {4, 5})

DFS 过程：
  dfn[1]=1, dfn[2]=2, dfn[3]=3, dfn[4]=4, dfn[5]=5
  low[5]=4, low[4]=4 → 弹出 {4,5} 构成 SCC2
  low[3]=1, low[2]=1, low[1]=1 → 弹出 {1,2,3} 构成 SCC1

12.1.4 代码实现¶

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

const int MAXN = 100010;

int n, m;
vector<int> G[MAXN];

int dfn[MAXN], low[MAXN], timer;
int stk[MAXN], top;         // 手写栈
bool in_stack[MAXN];        // 是否在栈中
int scc_id[MAXN], scc_cnt;  // 每个点所属 SCC 的编号
int scc_size[MAXN];         // 每个 SCC 的大小

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u;
    in_stack[u] = true;

    for (int v : G[u]) {
        if (!dfn[v]) {
            // 未访问过，递归
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            // 已访问且在栈中，是一条反向边
            low[u] = min(low[u], dfn[v]);
        }
    }

    // u 是当前 SCC 的根
    if (low[u] == dfn[u]) {
        scc_cnt++;
        while (true) {
            int v = stk[top--];
            in_stack[v] = false;
            scc_id[v] = scc_cnt;
            scc_size[scc_cnt]++;
            if (v == u) break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }

    // 输出每个 SCC 的大小
    for (int i = 1; i <= scc_cnt; i++) {
        cout << "SCC " << i << ": size=" << scc_size[i] << "\n";
    }
    return 0;
}

12.1.5 复杂度分析¶

指标	复杂度
时间	\(O(V + E)\)，每个点和边各访问一次
空间	\(O(V + E)\)，邻接栈 + 栈 + 数组

12.1.6 典型应用¶

缩点：将每个 SCC 缩成一个点，得到 DAG，然后可以在 DAG 上做 DP（详见 12.1.7）
2-SAT：利用 SCC 判断可行性（详见 12.1.8）
可达性计数：在缩点后的 DAG 上统计

12.1.7 SCC 应用一：缩点 + DAG 上 DP（洛谷 P3387）¶

概念引入：有向图上的路径问题（最长路、路径计数等）在一般图上因为有环而无法直接 DP。但注意到：同一个 SCC 内的点互相可达，走进一个 SCC 就能"免费"拿到其中所有点。于是标准套路是——

Tarjan 求出所有 SCC，把每个 SCC 缩成一个点，新点权 = SCC 内点权之和
遍历原图每条边 \((u, v)\)，若 scc_id[u] != scc_id[v]，在新图中连边（跨 SCC 的边）
新图是 DAG，按拓扑序做 DP

flowchart LR
    A["Tarjan 求 SCC"] --> B["缩点：新点权 = SCC 点权和"]
    B --> C["保留跨 SCC 的边，得到 DAG"]
    C --> D["按拓扑序 DP 求最长路"]

关键技巧：Tarjan 弹栈时先完成的 SCC 一定位于 DAG 的"下游"（汇的方向），因此 SCC 编号恰好是逆拓扑序——对新图中任意边 \(cu \to cv\)，必有 scc_id 满足 \(cu > cv\)。按编号从 scc_cnt 到 1 遍历即为拓扑序，无需再写一遍 Kahn 算法。

例题：洛谷 P3387【模板】缩点

题意：给定 \(n\) 个点 \(m\) 条边的有向图，每个点有点权（\(n \leq 10^4\)，\(m \leq 10^5\)）。从任意点出发沿有向边行走（点和边都可以重复经过），每个点的点权只计一次，求一条路径使点权之和最大。

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

const int MAXN = 10010;

int n, m;
int w[MAXN];                // 原图点权
vector<int> G[MAXN];        // 原图
pair<int, int> edges[100010]; // 保存原边，缩点后重建图用

int dfn[MAXN], low[MAXN], timer;
int stk[MAXN], top;
bool in_stack[MAXN];
int scc_id[MAXN], scc_cnt;
long long sw[MAXN];         // 每个 SCC 的点权和

vector<int> DAG[MAXN];      // 缩点后的新图
long long dp[MAXN];

void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u;
    in_stack[u] = true;

    for (int v : G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (low[u] == dfn[u]) {
        scc_cnt++;
        while (true) {
            int v = stk[top--];
            in_stack[v] = false;
            scc_id[v] = scc_cnt;
            sw[scc_cnt] += w[v];
            if (v == u) break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> w[i];
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        edges[i] = {u, v};
    }

    // 第一步：Tarjan 求 SCC
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }

    // 第二步：缩点建新图（只保留跨 SCC 的边）
    for (int i = 0; i < m; i++) {
        int cu = scc_id[edges[i].first], cv = scc_id[edges[i].second];
        if (cu != cv) DAG[cu].push_back(cv);
    }

    // 第三步：DAG 上 DP。SCC 编号是逆拓扑序，
    // 从 scc_cnt 到 1 遍历即为拓扑序
    long long ans = 0;
    for (int c = scc_cnt; c >= 1; c--) {
        dp[c] += sw[c];              // 走到 c，拿到整个 SCC 的点权
        ans = max(ans, dp[c]);
        for (int d : DAG[c]) {
            dp[d] = max(dp[d], dp[c]); // 松弛后继
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度分析

步骤	复杂度
Tarjan 求 SCC	\(O(V + E)\)
缩点建新图	\(O(V + E)\)
DAG 上 DP	\(O(V + E)\)
总计	\(O(V + E)\)

缩点常见坑

重边：缩点后新图可能出现重边。对最长路 DP 无影响（max 天然幂等），但路径计数类问题必须去重（可用 set 或排序去重），否则方案数会算多
自环：scc_id[u] == scc_id[v] 的边直接丢弃，不要加进新图
拓扑序方向：SCC 编号是逆拓扑序，DP 循环要从 scc_cnt 递减到 1；写反则所有转移全部失效，样例都过不了
爆栈：递归 Tarjan 在深链图上可能栈溢出，参见 11.3.1 节的处理方法

12.1.8 SCC 应用二：2-SAT（洛谷 P4782）¶

概念引入：2-SAT 问题：给定 \(n\) 个布尔变量 \(x_1, \dots, x_n\) 与 \(m\) 个形如 \((a \lor b)\) 的约束（每个约束恰含两个文字），判断是否存在一组赋值满足所有约束，并构造一组解。

建图规则：为每个变量 \(x_i\) 建两个节点：\(i\) 表示 \(x_i\) 为真，\(i + n\) 表示 \(x_i\) 为假。有向边 \(u \to v\) 的含义是"若 \(u\) 成立，则 \(v\) 必然成立"。于是每个子句转化为两条边：

约束	连边	含义
\(x \lor y\)	\(\lnot x \to y\)，\(\lnot y \to x\)	x 假则 y 必真；y 假则 x 必真
\(\lnot x \lor y\)	\(x \to y\)，\(\lnot y \to \lnot x\)	x 真则 y 必真（蕴含式 \(x \Rightarrow y\)）
\(x\) 必须为真	\(\lnot x \to x\)	x 假会推出矛盾，只能取真
\(x \ne y\)	\(x \to \lnot y\)，\(y \to \lnot x\)，\(\lnot x \to y\)，\(\lnot y \to x\)	两变量必取相反值

求解与判定：对建出的图跑 Tarjan 求 SCC。

可满足性判定：若存在某个 \(i\) 使 \(x_i\) 与 \(\lnot x_i\) 在同一个 SCC 中，则 \(x_i\) 为真能推出 \(x_i\) 为假（反之亦然），矛盾，无解；否则必然有解
构造方案：对每个变量，取其两个节点中拓扑序靠后（更靠近"汇"）的那个取值。Tarjan 的 SCC 编号是逆拓扑序，编号小 = 拓扑序靠后，因此取 scc_id[i] < scc_id[i + n] 时 \(x_i\) 为真，否则为假

flowchart TD
    A["每个子句 (a ∨ b) 连两条蕴含边"] --> B["Tarjan 求 SCC"]
    B --> C{"存在 x 与 ¬x 同 SCC?"}
    C -- 是 --> D["IMPOSSIBLE"]
    C -- 否 --> E["x 取 scc_id 较小（拓扑序靠后）的一侧"]
    E --> F["输出方案"]

例题：洛谷 P4782【模板】2-SAT

题意：\(n\) 个布尔变量，\(m\) 个约束。每个约束形如 i a j b，表示 \(x_i = a\) 或 \(x_j = b\)（\(a, b \in \{0, 1\}\)，\(n, m \leq 10^6\)）。判断可满足性；可满足时输出任意一组解。

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

const int MAXN = 2000010;   // 2n 个节点

int n, m;
vector<int> G[MAXN];

int dfn[MAXN], low[MAXN], timer;
int stk[MAXN], top;
bool in_stack[MAXN];
int scc_id[MAXN], scc_cnt;

// 节点编号：i 表示 x_i = 真，i + n 表示 x_i = 假
void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u;
    in_stack[u] = true;

    for (int v : G[u]) {
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (in_stack[v]) {
            low[u] = min(low[u], dfn[v]);
        }
    }

    if (low[u] == dfn[u]) {
        scc_cnt++;
        while (true) {
            int v = stk[top--];
            in_stack[v] = false;
            scc_id[v] = scc_cnt;
            if (v == u) break;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int k = 0; k < m; k++) {
        int i, a, j, b;
        cin >> i >> a >> j >> b;  // 子句：x_i = a 或 x_j = b
        // (x_i != a) => (x_j = b)，以及对称的 (x_j != b) => (x_i = a)
        int u_false = a ? i + n : i;   // "x_i != a" 对应的节点
        int u_true  = a ? i : i + n;   // "x_i = a"  对应的节点
        int v_false = b ? j + n : j;
        int v_true  = b ? j : j + n;
        G[u_false].push_back(v_true);
        G[v_false].push_back(u_true);
    }

    for (int i = 1; i <= 2 * n; i++) {
        if (!dfn[i]) tarjan(i);
    }

    // 判定：x_i 与 ¬x_i 同一 SCC 则无解
    for (int i = 1; i <= n; i++) {
        if (scc_id[i] == scc_id[i + n]) {
            cout << "IMPOSSIBLE\n";
            return 0;
        }
    }

    // 构造方案：取拓扑序靠后（scc_id 较小）的取值
    cout << "POSSIBLE\n";
    for (int i = 1; i <= n; i++) {
        cout << (scc_id[i] < scc_id[i + n] ? 1 : 0) << " \n"[i == n];
    }
    return 0;
}

复杂度分析

指标	复杂度
建图	\(O(n + m)\)，共 \(2n\) 个节点、\(2m\) 条边
Tarjan + 判定 + 构造	\(O(n + m)\)

2-SAT 常见坑

两条边都要加：子句 \((a \lor b)\) 对应 \(\lnot a \to b\) 和 \(\lnot b \to a\) 两条边，只加一条是高频错误（图不再对称，判定会出错）
节点编号：始终约定 \(i\) = 真、\(i + n\) = 假，建图与输出两处必须一致
输出任意解即可：2-SAT 的解通常不唯一，与题目样例输出不同不代表错误，洛谷 P4782 使用 Special Judge
爆栈：本题 \(n, m\) 可达 \(10^6\)，递归 Tarjan 深度可达 \(2 \times 10^6\)，评测环境栈空间不足时需改为手写栈的迭代 Tarjan（或参见 11.3.1 节扩栈方法）

12.2 割点与桥¶

12.2.1 基本概念¶

给定一张无向连通图：

割点（Articulation Point）：删除该点后图不再连通
桥（Bridge）：删除该边后图不再连通

两者都是图的"脆弱点"，在网络可靠性、关键路径分析中非常重要。

12.2.2 Tarjan 算法求割点与桥¶

同样使用 dfn 和 low 数组：

桥判定：对于边 \((u, v)\)（\(u\) 是 \(v\) 的父），若 low[v] > dfn[u]，则 \((u, v)\) 是桥
割点判定：
- 若 \(u\) 是 DFS 树的根且有 至少两个 子树，则 \(u\) 是割点
- 若 \(u\) 不是根，且存在子节点 \(v\) 使得 low[v] >= dfn[u]，则 \(u\) 是割点

flowchart LR
    subgraph 桥的判定
        A["边 u→v"] --> B{"low[v] > dfn[u] ?"}
        B -- 是 --> C["是桥 ✅"]
        B -- 否 --> D["不是桥 ❌"]
    end
    subgraph 割点的判定
        E["点 u"] --> F{"u 是根?"}
        F -- 是 --> G{"子树数 ≥ 2 ?"}
        G -- 是 --> H["是割点 ✅"]
        F -- 否 --> I{"存在 low[v] ≥ dfn[u] ?"}
        I -- 是 --> H
    end

12.2.3 图解¶

无向图（5 个点，5 条边）：
  1 - 2 - 3
      |   |
      5 - 4

边集：{ (1,2), (2,3), (3,4), (4,5), (5,2) }

DFS 树（以 1 为根）：
  1 → 2 → 3 → 4 → 5，另有一条回边 5 → 2

DFS 按 \(1 \to 2 \to 3 \to 4 \to 5\) 的顺序展开，回边 \(5 \to 2\) 使 low[5] = dfn[2] = 2，并沿树边一路向上传递给 4、3、2：

节点 \(u\)	1	2	3	4	5
`dfn[u]`	1	2	3	4	5
`low[u]`	1	2	2	2	2

逐边判定桥（对树边 \((u, v)\)，\(u\) 为父，判 low[v] > dfn[u]）：

树边 \((u, v)\)	`low[v]`	`dfn[u]`	`low[v] > dfn[u]`？	结论
\((1, 2)\)	2	1	是	是桥
\((2, 3)\)	2	2	否	不是桥
\((3, 4)\)	2	3	否	不是桥
\((4, 5)\)	2	4	否	不是桥

环 \(2 - 3 - 4 - 5 - 2\) 上的四条边都不是桥（环上任删一条边仍连通）；只有"悬挂"在环外的 \((1, 2)\) 是桥，删掉后 \(\{1\}\) 与 \(\{2, 3, 4, 5\}\) 不连通。

逐点判定割点：

节点 \(u\)	判定过程	结论
1（根）	DFS 树中只有 1 个子树（child_cnt = 1 < 2）	不是割点
2	非根，子节点 3 满足 `low[3] = 2 >= dfn[2] = 2`	是割点
3	非根，子节点 4：`low[4] = 2 < dfn[3] = 3`	不是割点
4	非根，子节点 5：`low[5] = 2 < dfn[4] = 4`	不是割点
5	叶子节点，无子树	不是割点

验证：删除点 2 后，点 1 与 \(\{3, 4, 5\}\) 不连通，2 确实是全图唯一的割点。

12.2.4 代码实现¶

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

const int MAXN = 100010;

int n, m;
vector<int> G[MAXN];

int dfn[MAXN], low[MAXN], timer;
bool is_cut[MAXN];          // 是否是割点
vector<pair<int, int>> bridges; // 存储所有桥

void tarjan(int u, int fa) {
    dfn[u] = low[u] = ++timer;
    int child_cnt = 0;  // DFS 树中 u 的子树数量

    for (int v : G[u]) {
        if (v == fa) continue;  // 无向图不能走回父节点
        // 注意：遇到重边（u、v 之间有多条边）时，这种写法会把重边也误跳过，
        // 导致漏判——严格做法是记录"来时的边编号"，只跳过那一条边（见 12.3 节写法）

        if (!dfn[v]) {
            child_cnt++;
            tarjan(v, u);
            low[u] = min(low[u], low[v]);

            // 割点判定：根需要至少两个子树；非根看 low[v] >= dfn[u]
            if (fa == -1 && child_cnt >= 2) {
                is_cut[u] = true;
            }
            if (fa != -1 && low[v] >= dfn[u]) {
                is_cut[u] = true;
            }

            // 桥判定：low[v] > dfn[u]
            if (low[v] > dfn[u]) {
                bridges.push_back({min(u, v), max(u, v)});
            }
        } else {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i, -1);
    }

    // 输出割点
    cout << "割点: ";
    for (int i = 1; i <= n; i++) {
        if (is_cut[i]) cout << i << " ";
    }
    cout << "\n";

    // 输出桥
    cout << "桥: ";
    for (auto &[u, v] : bridges) {
        cout << "(" << u << "," << v << ") ";
    }
    cout << "\n";

    return 0;
}

12.2.5 复杂度分析¶

指标	复杂度
时间	\(O(V + E)\)
空间	\(O(V + E)\)

12.2.6 注意事项¶

无向图 DFS 时需要传父节点 fa 防止走回头路
判定桥时，low[v] > dfn[u] 是 严格大于，>= 不行
重边需要特别处理（用边编号标记而不只是跳过父节点）

12.3 边双连通分量¶

12.3.1 基本概念¶

边双连通分量（e-DCC）：极大子图，其中任意两点之间都存在至少两条边不相交的路径。等价说法：子图中不含桥。

缩去所有桥后，每个连通块就是一个边双连通分量。

12.3.2 求法¶

利用 12.2 节的桥判定：

Tarjan 找出所有桥
删除所有桥
DFS/BFS 遍历连通块，每个连通块即为一个 e-DCC

更优写法：在 Tarjan 过程中，用栈保存访问过的边，当 low[v] > dfn[u] 时弹出边形成 e-DCC。

flowchart TD
    A["Tarjan 求所有桥"] --> B["删除桥边"]
    B --> C["DFS 标记连通块"]
    C --> D["每个连通块 = 一个 e-DCC"]

12.3.3 代码实现¶

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

const int MAXN = 100010;
const int MAXM = 200010;

int n, m;
int head[MAXN], nxt[MAXM * 2], to[MAXM * 2], edge_cnt = 1;
// 使用边编号，从 2 开始（^1 得反向边）

int dfn[MAXN], low[MAXN], timer;
bool is_bridge[MAXM * 2];

// 边双相关
int dcc_id[MAXN], dcc_cnt;
vector<int> dcc[MAXN];

void add_edge(int u, int v) {
    nxt[++edge_cnt] = head[u];
    head[u] = edge_cnt;
    to[edge_cnt] = v;
}

void tarjan(int u, int from_edge) {
    dfn[u] = low[u] = ++timer;
    for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        if (!dfn[v]) {
            tarjan(v, e);
            low[u] = min(low[u], low[v]);
            if (low[v] > dfn[u]) {
                is_bridge[e] = is_bridge[e ^ 1] = true;
            }
        } else if (e != (from_edge ^ 1)) {
            low[u] = min(low[u], dfn[v]);
        }
    }
}

void dfs_dcc(int u) {
    dcc_id[u] = dcc_cnt;
    dcc[dcc_cnt].push_back(u);
    for (int e = head[u]; e; e = nxt[e]) {
        if (is_bridge[e]) continue;
        int v = to[e];
        if (!dcc_id[v]) dfs_dcc(v);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        add_edge(u, v);
        add_edge(v, u);
    }

    // 第一步：Tarjan 求桥
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i, 0);
    }

    // 第二步：跳过桥，DFS 求 e-DCC
    for (int i = 1; i <= n; i++) {
        if (!dcc_id[i]) {
            dcc_cnt++;
            dfs_dcc(i);
        }
    }

    cout << "边双连通分量数量: " << dcc_cnt << "\n";
    for (int i = 1; i <= dcc_cnt; i++) {
        cout << "e-DCC " << i << ": ";
        for (int v : dcc[i]) cout << v << " ";
        cout << "\n";
    }

    return 0;
}

12.3.4 复杂度分析¶

指标	复杂度
时间	\(O(V + E)\)
空间	\(O(V + E)\)

12.3.5 e-DCC 缩点¶

将每个 e-DCC 缩成一个点后，原图变成一棵树（因为桥连接的恰好是缩点后的树边）。这在树上问题中非常有用。

12.4 二分图¶

12.4.1 基本概念¶

二分图（Bipartite Graph）：顶点集可分成两个不相交的集合 \(U\) 和 \(V\)，使得每条边的两个端点分别属于 \(U\) 和 \(V\)。

等价条件：图中不含奇数长度的环。

graph LR
    subgraph 左集合 U
        u1((1))
        u2((2))
        u3((3))
    end
    subgraph 右集合 V
        v1((4))
        v2((5))
        v3((6))
    end
    u1 --- v1
    u1 --- v2
    u2 --- v1
    u2 --- v3
    u3 --- v2

12.4.2 二分图判定 — 染色法¶

原理：用两种颜色（0 和 1）给图染色，若相邻节点颜色不同则图是二分图。

flowchart TD
    A["从任意未染色点 u 出发，染色为 0"] --> B["BFS/DFS 遍历邻接点 v"]
    B --> C{"v 已染色?"}
    C -- 否 --> D["v 染相反颜色，入队"]
    C -- 是 --> E{"v 颜色与 u 相同?"}
    E -- 是 --> F["矛盾！不是二分图 ❌"]
    E -- 否 --> G["继续遍历"]
    D --> G

12.4.3 染色法代码¶

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

const int MAXN = 100010;

int n, m;
vector<int> G[MAXN];
int color[MAXN]; // 0: 未染色, 1: 颜色A, -1: 颜色B

bool bfs_check(int start) {
    queue<int> q;
    color[start] = 1;
    q.push(start);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : G[u]) {
            if (!color[v]) {
                color[v] = -color[u];
                q.push(v);
            } else if (color[v] == color[u]) {
                return false; // 相邻同色，不是二分图
            }
        }
    }
    return true;
}

bool is_bipartite() {
    memset(color, 0, sizeof(color));
    for (int i = 1; i <= n; i++) {
        if (!color[i] && !bfs_check(i)) {
            return false;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    if (is_bipartite()) {
        cout << "是二分图\n";
    } else {
        cout << "不是二分图\n";
    }
    return 0;
}

12.4.4 匈牙利算法（最大匹配）¶

问题：在二分图中，找出最多数量的边，使得没有两条边共享同一个端点。

增广路思想：从左部未匹配点出发，寻找一条交替路径（匹配边 → 非匹配边 → ...），若终点是右部未匹配点，则路径上所有边的状态翻转，匹配数 +1。

flowchart TD
    A["对左部每个未匹配点 u"] --> B["DFS 寻找增广路"]
    B --> C["遍历 u 的邻接点 v"]
    C --> D{"v 在本轮已访问?"}
    D -- 是 --> C
    D -- 否 --> E{"v 未匹配?"}
    E -- 是 --> F["直接匹配 u-v，成功 ✅"]
    E -- 否 --> G["尝试让 v 的原匹配对象 match[v] 换人"]
    G --> H{"match[v] 能找到新匹配?"}
    H -- 是 --> F
    H -- 否 --> C

12.4.5 图解匈牙利算法¶

左部: {1, 2, 3}   右部: {4, 5, 6}
边: 1-4, 1-5, 2-4, 2-6, 3-5

第1轮：dfs(1)：1 找 4 → 4 空闲 → 匹配 (1,4)

第2轮：dfs(2)：2 找 4 → 4 已配给 1 → 递归 dfs(1) 让 1 换人：
       1 找 5 → 5 空闲 → 换人成功
       → 匹配变为 (1,5), (2,4)

第3轮：dfs(3)：3 找 5 → 5 已配给 1 → 递归 dfs(1) 让 1 换人：
       1 找 4 → 4 已配给 2 → 递归 dfs(2) 让 2 换人：
       2 找 6 → 6 空闲 → 换人成功
       → 沿增广路 3→5→1→4→2→6 依次翻转，
         匹配变为 (1,4), (2,6), (3,5)

最大匹配 = 3

第 3 轮的连锁"换人"正是增广路思想：路径 \(3 \to 5 \to 1 \to 4 \to 2 \to 6\) 上非匹配边与匹配边交替出现，整体翻转后匹配数恰好 +1。每一轮 DFS 要么失败（匹配数不变），要么找到一条增广路使匹配数 +1，因此三个左部点全部匹配成功，最大匹配为 3。

12.4.6 匈牙利算法代码¶

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

const int MAXN = 510;  // 左部节点数
const int MAXM = 510;  // 右部节点数

int n, m, edge_count;
vector<int> G[MAXN];   // G[i]: 左部节点 i 连向的右部节点列表
int match[MAXM];       // match[v]: 右部节点 v 当前匹配的左部节点
bool vis[MAXM];        // 本轮 DFS 中右部节点是否已访问

bool dfs(int u) {
    for (int v : G[u]) {
        if (vis[v]) continue;
        vis[v] = true;
        // v 未匹配，或者 v 的原匹配对象可以换人
        if (!match[v] || dfs(match[v])) {
            match[v] = u;
            return true;
        }
    }
    return false;
}

int hungarian() {
    int res = 0;
    memset(match, 0, sizeof(match));
    for (int u = 1; u <= n; u++) {
        memset(vis, false, sizeof(vis));
        if (dfs(u)) res++;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> edge_count;
    for (int i = 0; i < edge_count; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
    }

    cout << "最大匹配: " << hungarian() << "\n";
    return 0;
}

12.4.7 复杂度分析¶

算法	时间	空间
染色法判定	\(O(V + E)\)	\(O(V)\)
匈牙利算法	\(O(VE)\)（最坏）	\(O(V + E)\)

12.4.8 常见应用¶

最大匹配：任务分配、棋盘覆盖
最小点覆盖 = 最大匹配（Konig 定理，二分图上成立）
最大独立集 = \(V\) - 最小点覆盖
DAG 最小路径覆盖 = \(V\) - 拆点后的最大匹配

12.5 网络流简介¶

12.5.1 基本概念¶

网络流是一张有向图，其中：

源点 \(s\)：只出不进
汇点 \(t\)：只进不出
容量 \(c(u, v)\)：每条边的最大流量
流 \(f(u, v)\)：实际通过的流量，需满足 \(0 \le f \le c\)

最大流问题：从 \(s\) 到 \(t\) 的最大流量。

graph LR
    s((s)) -- "10/16" --> A((A))
    s -- "10/13" --> B((B))
    A -- "12/12" --> B
    A -- "0/4" --> t((t))
    B -- "15/15" --> t
    A -- "11/14" --> C((C))
    C -- "15/20" --> t
    B -- "4/7" --> C

12.5.2 基本定理¶

最大流最小割定理：最大流 = 最小割（Ford-Fulkerson 定理）。

12.5.3 Dinic 算法¶

Dinic 是竞赛中最常用的网络流算法，核心思想：

BFS 建分层图：从 \(s\) 出发 BFS，记录每个点的层次（到 \(s\) 的最短距离）
DFS 多路增广：在分层图上 DFS，沿层次严格递增的方向增广
重复直到无法到达 \(t\)

优化：当前弧优化（cur[u] 记录 \(u\) 的当前遍历位置，跳过已满的边）

flowchart TD
    A["BFS 建分层图 dist[]"] --> B{"t 可达?"}
    B -- 否 --> C["算法结束，返回最大流"]
    B -- 是 --> D["重置 cur[] 数组"]
    D --> E["DFS 多路增广：从 s 到 t 找阻塞流"]
    E --> F["累加增广量到总流"]
    F --> A

12.5.4 代码实现¶

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

const int MAXN = 10010;
const int MAXM = 200010;
const int INF = 1e9;

int n, m, s, t;

// 链式前向星存图
int head[MAXN], nxt[MAXM], to[MAXM], cap[MAXM];
int edge_cnt = 1;  // 从 2 开始编号，方便取反向边

int dist[MAXN];    // BFS 分层
int cur[MAXN];     // 当前弧优化

void add_edge(int u, int v, int w) {
    nxt[++edge_cnt] = head[u];
    head[u] = edge_cnt;
    to[edge_cnt] = v;
    cap[edge_cnt] = w;
}

// BFS 建分层图
bool bfs() {
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int e = head[u]; e; e = nxt[e]) {
            int v = to[e];
            if (cap[e] > 0 && dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
    return dist[t] != -1;
}

// DFS 多路增广，flow 是当前路径上的最小剩余容量
int dfs(int u, int flow) {
    if (u == t) return flow;  // 到达汇点

    int total = 0;
    for (int e = cur[u]; e && flow > 0; e = nxt[e]) {
        cur[u] = e;  // 当前弧优化
        int v = to[e];
        if (cap[e] > 0 && dist[v] == dist[u] + 1) {
            int pushed = dfs(v, min(flow, cap[e]));
            if (pushed > 0) {
                cap[e] -= pushed;
                cap[e ^ 1] += pushed;  // 反向边
                total += pushed;
                flow -= pushed;
            }
        }
    }
    return total;
}

int dinic() {
    int max_flow = 0;
    while (bfs()) {
        // 复制 head 到 cur
        for (int i = 1; i <= n; i++) cur[i] = head[i];
        max_flow += dfs(s, INF);
    }
    return max_flow;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> s >> t;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        add_edge(u, v, w);  // 正向边
        add_edge(v, u, 0);  // 反向边，初始容量 0
    }

    cout << dinic() << "\n";
    return 0;
}

12.5.5 复杂度分析¶

指标	复杂度
时间	\(O(V^2 E)\)（一般远好于此）
实际竞赛	千点万量级的图轻松通过

12.5.6 竞赛中的网络流¶

二分图最大匹配：源连左部，右部连汇，容量为 1，最大流 = 最大匹配
最大权闭合子图：最小割模型
费用流：每次增广选最短路（SPFA/Dijkstra），解决最小费用最大流

12.6 树上技巧¶

12.6.1 树的直径¶

定义：树上最长的简单路径（即经过边数最多的两点之间的路径）。

两次 BFS/DFS 法：

flowchart LR
    A["任选一点 u"] --> B["BFS/DFS 找离 u 最远的点 v"]
    B --> C["BFS/DFS 找离 v 最远的点 w"]
    C --> D["v 到 w 的距离 = 树的直径"]

正确性：两次 BFS 法基于一个关键性质：对于任意点 \(u\)，离 \(u\) 最远的点 \(v\) 一定是直径的一个端点。

负权边下两次 BFS 失效

上述关键性质只在边权非负时成立。若树上存在负权边，"离 \(u\) 最远的点是直径端点"不再保证，两次 BFS/DFS 法会得到错误答案，此时需改用树形 DP 求直径：对每个点维护向下的最长与次长路径，用两者之和更新答案。

12.6.2 树直径代码¶

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

const int MAXN = 100010;

int n;
vector<pair<int, int>> G[MAXN]; // (邻接点, 边权)
int dist[MAXN];

int bfs(int start) {
    memset(dist, -1, sizeof(dist));
    queue<int> q;
    dist[start] = 0;
    q.push(start);

    int farthest = start;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        if (dist[u] > dist[farthest]) farthest = u;
        for (auto &[v, w] : G[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + w;
                q.push(v);
            }
        }
    }
    return farthest;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back({v, w});
        G[v].push_back({u, w});
    }

    int v = bfs(1);    // 第一次 BFS
    int w = bfs(v);    // 第二次 BFS

    cout << "树的直径: " << dist[w] << "\n";
    return 0;
}

复杂度：\(O(V + E) = O(V)\)（树的 \(E = V - 1\)）

12.6.3 LCA — 倍增法¶

问题：给定树上两点 \(u, v\)，求它们的最近公共祖先（Lowest Common Ancestor, LCA）。

倍增法原理：

预处理 anc[u][k] 表示 \(u\) 向上跳 \(2^k\) 步到达的祖先。查询时，利用二进制拆分，从大到小尝试跳跃。

flowchart TD
    subgraph 预处理
        A["DFS 记录每个点的深度 dep[u]"] --> B["anc[u][0] = 父节点"]
        B --> C["anc[u][k] = anc[anc[u][k-1]][k-1]"]
    end
    subgraph 查询 LCA_u_v
        D["先将较深的点向上跳到同一层"] --> E["从大到小枚举 k"]
        E --> F{"anc[u][k] != anc[v][k]?"}
        F -- 是 --> G["u, v 同时跳 2^k 步"]
        G --> E
        F -- 否 --> H["跳过，试更小的 k"]
        H --> E
        E --> I["返回 anc[u][0]（即 LCA）"]
    end

12.6.4 图解倍增¶

树：    1
       / \
      2   3
     / \   \
    4   5   6

LCA(4, 5) = 2
LCA(4, 6) = 1
LCA(5, 6) = 1

anc 数组：
anc[4][0] = 2, anc[4][1] = 1, anc[4][2] = 0
anc[5][0] = 2, anc[5][1] = 1
anc[6][0] = 3, anc[6][1] = 1

求 LCA(4, 6)：
  dep[4]=3, dep[6]=3 → 同层
  k=1: anc[4][1]=1, anc[6][1]=1 → 相等，不跳
  k=0: anc[4][0]=2, anc[6][0]=3 → 不等，跳！
       → u=2, v=3
  返回 anc[2][0] = 1 ✓

12.6.5 LCA 倍增代码¶

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

const int MAXN = 100010;
const int LOG = 20;  // log2(MAXN) ≈ 17，取 20 留余量

int n, m, root;
vector<int> G[MAXN];

int dep[MAXN];          // 深度
int anc[MAXN][LOG];     // 倍增数组

void dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    anc[u][0] = fa;
    for (int k = 1; k < LOG; k++) {
        anc[u][k] = anc[anc[u][k - 1]][k - 1];
    }
    for (int v : G[u]) {
        if (v != fa) dfs(v, u);
    }
}

int lca(int u, int v) {
    // 1. 将较深的点上提到同一层
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = LOG - 1; k >= 0; k--) {
        if ((diff >> k) & 1) {
            u = anc[u][k];
        }
    }
    if (u == v) return u;

    // 2. 从大到小倍增，找到 LCA 的下一层
    for (int k = LOG - 1; k >= 0; k--) {
        if (anc[u][k] != anc[v][k]) {
            u = anc[u][k];
            v = anc[v][k];
        }
    }
    return anc[u][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> root;
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dep[0] = 0;
    dfs(root, 0);

    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }
    return 0;
}

复杂度：

指标	复杂度
预处理	\(O(V \log V)\)
单次查询	\(O(\log V)\)

12.6.6 树链剖分简介¶

树链剖分（Heavy-Light Decomposition, HLD）：将树分解为若干条链，使得任意两点间的路径可拆成 \(O(\log V)\) 条链的拼接，从而结合线段树完成路径上的区间查询与修改。

核心概念：

重儿子：父节点所有儿子中子树大小最大的那个
轻儿子：非重儿子
重链：由重儿子串起来的链
轻边：连接父节点和轻儿子的边

graph TD
    A((1)) --> B((2))
    A --> C((3))
    A --> D((4))
    B --> E((5))
    B --> F((6))
    C --> G((7))

    style A fill:#4CAF50,color:white
    style B fill:#2196F3,color:white
    style E fill:#2196F3,color:white
    style C fill:#FF9800,color:white
    style G fill:#FF9800,color:white
    style D fill:#9C27B0,color:white
    style F fill:#FF5722,color:white

上图中，假设子树大小：2 最大（以 A 为根），则 B 是 A 的重儿子。重链可能是 1-2-5。

关键性质：从任意节点到根的路径上，至多经过 \(O(\log V)\) 条重链（每次走轻边，子树大小至少减半）。

12.6.7 树链剖分代码框架¶

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

const int MAXN = 100010;

int n, m, root;
int val[MAXN];
vector<int> G[MAXN];

// 树剖数组
int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN];  // 父、深、子树大小、重儿子
int top[MAXN];    // 所在重链的顶部节点
int dfn[MAXN];    // DFS 序编号
int rnk[MAXN];    // DFS 序编号对应的节点（反向映射）
int timer;

// === 第一遍 DFS：求 fa, dep, sz, son ===
void dfs1(int u, int f) {
    fa[u] = f;
    dep[u] = dep[f] + 1;
    sz[u] = 1;
    son[u] = 0;
    int max_sz = 0;
    for (int v : G[u]) {
        if (v == f) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > max_sz) {
            max_sz = sz[v];
            son[u] = v;
        }
    }
}

// === 第二遍 DFS：求 top, dfn, rnk ===
void dfs2(int u, int t) {
    top[u] = t;        // 当前链顶
    dfn[u] = ++timer;
    rnk[timer] = u;

    if (son[u]) {
        dfs2(son[u], t);   // 重儿子继承当前链顶
        for (int v : G[u]) {
            if (v == fa[u] || v == son[u]) continue;
            dfs2(v, v);    // 轻儿子开新链，链顶是自己
        }
    }
}

// === 求路径 u-v 上的信息（结合线段树）===
// 将路径拆成若干段 [dfn[top[x]], dfn[x]]，在 DFS 序上做区间操作
int query_path(int u, int v) {
    int res = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        // [dfn[top[u]], dfn[u]] 这段在同一条重链上
        // res = max(res, seg.query(dfn[top[u]], dfn[u]));
        u = fa[top[u]];
    }
    // u, v 在同一条重链上
    if (dep[u] > dep[v]) swap(u, v);
    // res = max(res, seg.query(dfn[u], dfn[v]));
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> root;
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs1(root, 0);
    dfs2(root, root);

    // 此后可以用 dfn 序 + 线段树维护路径/子树信息
    // query_path(u, v) 可在 O(log^2 n) 内完成路径查询
    return 0;
}

复杂度：

操作	复杂度
预处理	\(O(V)\)
路径查询/修改	\(O(\log^2 V)\)（配合线段树）
子树查询/修改	\(O(\log V)\)（子树在 DFS 序上连续）

12.7 虚拟节点技巧¶

12.7.1 什么是虚拟节点¶

虚拟节点（Dummy Node / Virtual Node）是图论建模中的重要技巧：在原图中添加辅助节点来简化问题结构。

常见的使用场景：

多源最短路：添加超级源点，连向所有源点，边权为 0
最小生成树建模：添加虚拟节点连接若干组节点
分层图：在每层图之间添加虚拟边表示状态转移

12.7.2 典型用法一：多源 BFS / 最短路¶

问题：给定多个起点，求每个点到最近起点的距离。

做法：添加一个虚拟源点 \(s\)，令 \(s\) 到每个起点的边权为 0，然后从 \(s\) 做一次 Dijkstra/BFS。

graph TD
    subgraph 原图
        A((1))
        B((2))
        C((3))
        D((4))
    end
    subgraph 添加虚拟源
        S((s)) -- "0" --> A
        S -- "0" --> C
    end

12.7.3 典型用法二：虚树¶

在涉及树上若干关键节点的查询问题中，若关键节点总数为 \(k\)，全树节点数为 \(n\)，暴力处理 \(O(n)\) 无法接受。

虚树（Virtual Tree）只保留关键节点及其 LCA，将 \(k\) 个关键节点压缩成 \(O(k)\) 个节点的树。

flowchart LR
    A["将关键节点按 DFS 序排序"] --> B["用栈维护当前虚树的右链"]
    B --> C["逐个加入关键节点，LCA 用倍增求"]
    C --> D["在虚树上做 DP / 暴力"]

虚树建树代码框架：

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

const int MAXN = 100010;
const int LOG = 20;

int n, m;
vector<int> G[MAXN];
int dep[MAXN], anc[MAXN][LOG], dfn[MAXN], timer;

void dfs(int u, int fa) {
    dfn[u] = ++timer;
    dep[u] = dep[fa] + 1;
    anc[u][0] = fa;
    for (int k = 1; k < LOG; k++) {
        anc[u][k] = anc[anc[u][k - 1]][k - 1];
    }
    for (int v : G[u]) {
        if (v != fa) dfs(v, u);
    }
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    int diff = dep[u] - dep[v];
    for (int k = LOG - 1; k >= 0; k--) {
        if ((diff >> k) & 1) u = anc[u][k];
    }
    if (u == v) return u;
    for (int k = LOG - 1; k >= 0; k--) {
        if (anc[u][k] != anc[v][k]) {
            u = anc[u][k];
            v = anc[v][k];
        }
    }
    return anc[u][0];
}

// === 虚树部分 ===
vector<int> vt[MAXN];   // 虚树邻接表
bool is_key[MAXN];       // 是否是关键节点
int stk[MAXN], top;      // 用栈维护虚树

// 按 DFS 序排序
bool cmp_dfn(int a, int b) {
    return dfn[a] < dfn[b];
}

void build_virtual_tree(vector<int>& key_nodes) {
    // 加入根节点（防止某些 LCA 未加入）
    key_nodes.push_back(1);
    sort(key_nodes.begin(), key_nodes.end(), cmp_dfn);
    // 去重
    key_nodes.erase(unique(key_nodes.begin(), key_nodes.end()), key_nodes.end());

    top = 0;
    stk[++top] = key_nodes[0];

    for (int i = 1; i < (int)key_nodes.size(); i++) {
        int u = key_nodes[i];
        int l = lca(u, stk[top]);

        // 当栈中第二个点深度 >= lca 深度时，可以连边
        while (top > 1 && dep[stk[top - 1]] >= dep[l]) {
            vt[stk[top - 1]].push_back(stk[top]);
            top--;
        }
        // 栈顶不是 lca，说明 lca 还没入栈
        if (dep[stk[top]] > dep[l]) {
            vt[l].push_back(stk[top]);
            top--;
            if (stk[top] != l) stk[++top] = l;
        }
        stk[++top] = u;
    }

    // 收尾：栈中剩余节点相连
    while (top > 1) {
        vt[stk[top - 1]].push_back(stk[top]);
        top--;
    }
}

void clear_virtual_tree(vector<int>& key_nodes) {
    for (int u : key_nodes) {
        vt[u].clear();
    }
}

复杂度：

指标	复杂度
建虚树	\(O(k \log k)\)（排序 + 逐个求 LCA）
虚树大小	\(O(k)\) 个节点和边

12.7.4 典型用法三：分层图最短路¶

问题：在原图上，你可以免费走 \(k\) 条边（或以不同代价使用若干次特殊能力），求最短路。

做法：建 \(k + 1\) 层图，每层是原图的复制。对于原图中的边 \((u, v)\)，在第 \(i\) 层保留原边权，同时添加第 \(i\) 层 \(u\) 到第 \(i + 1\) 层 \(v\) 的边（权为 0 或折扣权），表示使用一次特殊能力。

// 分层图节点编号：layer * (n + 1) + u
// 共 (k + 1) 层，每层 n 个节点
// 原图边 (u,v,w) 在每层都添加
// 特殊边从第 i 层 u 到第 i+1 层 v，权为 0（免费通过）
int node_id(int layer, int u) {
    return layer * (n + 1) + u;
}

// 建图时：
// 第 i 层 (0 <= i <= k):
//   原边: node_id(i, u) -> node_id(i, v), 权 w
//   跳层边（若 i < k）: node_id(i, u) -> node_id(i+1, v), 权 0（免费）
// 起点: node_id(0, s)
// 终点: min(node_id(i, t)) for i in [0, k]

12.7.5 虚拟节点技巧总结¶

场景	做法	效果
多源最短路	虚拟源点连 0 边	一次 Dijkstra 解决
虚树	保留关键点 + LCA，压缩树	\(O(n) \to O(k \log k)\)
分层图	\(k+1\) 层图，层间连特殊边	用最短路解决含限制的图问题
最小生成树	虚拟点连一组点	将分组连接问题转化为 MST

综合练习题¶

Day 7 图论进阶（12 题）¶

以下是本章配套练习，覆盖 SCC、割点与桥、二分图、网络流、树上技巧等内容。

Codeforces 题目¶

题号	题目	核心知识点	难度
CF1245D	Shichikuji and Power Grid	虚拟节点 + MST	1700
CF427C	Checkposts	强连通分量（Tarjan SCC）	1700
CF1986F	Non-academic Problem	割边 / 桥	2000
CF770C	Online Courses in BSU	拓扑排序 + SCC（有向图判环）	1800
CF1931F	Chat Screenshots	有向图 / 拓扑序 / 判环	1700
CF1991D	Prime XOR Coloring	二分图 / 图着色	2000
CF1927F	Microcycle	最小环 / DFS / 边权最小	2100

AtCoder 题目¶

题号	题目	核心知识点	难度
ABC277D	Takahashi's Solitaire	环 / 连通分量 / 贪心	黄
ARC111B	Reversible Cards	边双连通分量 / 并查集	绿
ABC265D	Iroha and Haiku	前缀和 + 图建模 / 搜索	黄

洛谷题目¶

题号	题目	核心知识点	难度
P2661	信息传递	最小环 / 并查集 / 拓扑排序	普及+/提高
P1347	旅行	拓扑排序 + 判环 + 二分图	提高+/省选

解题要点提示¶

CF427C Checkposts：缩点后，每个 SCC 中权值最小的点必选。答案 = 最小权值之和 × 方案数（取模）。

CF1986F Non-academic Problem：先 Tarjan 找所有桥，再对每个 e-DCC 计算点数 \(c\)，该分量内可以贡献 \(c \times (n - c)\) 条非学术路径。不需要删的边是答案。

ARC111B Reversible Cards：将卡片看作边 \((a_i, b_i)\)，问题转化为无向图中找到最大边集，使得每个连通分量的边数不超过点数（即不含环）。每个分量贡献 \(\min(|V|, |E|)\) 条边。

P2661 信息传递：每个人传递给下一个人，构成有向图，找最小环。拓扑排序删点后，剩余的点一定在环上，DFS 找最小环即可。

CF1245D Power Grid：新建一个虚拟节点作为发电站，每个城市建发电站相当于连接到虚拟节点（边权为 \(c_i\)），拉电线是连接两个城市。问题转化为最小生成树，用 Kruskal 即可。

学习建议¶

SCC 和缩点是图论的基础技能，务必熟练手写 Tarjan
割点与桥常与边双连通分量一起考察，掌握 dfn/low 的本质
二分图是建模利器，匈牙利算法虽慢但思想重要，复杂情况可转网络流
网络流是图论的高级武器，Dinic 是竞赛标配，建模能力是关键
树上技巧（直径、LCA、树链剖分）是数据结构题的常客，倍增法最通用
虚拟节点是建模思维的体现，多源最短路、虚树、分层图都是常见套路

第十二章 图论进阶¶

12.1 强连通分量（SCC）¶

12.1.1 问题引入¶

12.1.2 Tarjan 算法原理¶

12.1.3 图解¶

12.1.4 代码实现¶

12.1.5 复杂度分析¶

12.1.6 典型应用¶

12.1.7 SCC 应用一：缩点 + DAG 上 DP（洛谷 P3387）¶

12.1.8 SCC 应用二：2-SAT（洛谷 P4782）¶

12.2 割点与桥¶

12.2.1 基本概念¶

12.2.2 Tarjan 算法求割点与桥¶

12.2.3 图解¶

12.2.4 代码实现¶

12.2.5 复杂度分析¶

12.2.6 注意事项¶

12.3 边双连通分量¶

12.3.1 基本概念¶

12.3.2 求法¶

12.3.3 代码实现¶

12.3.4 复杂度分析¶

12.3.5 e-DCC 缩点¶

12.4 二分图¶

12.4.1 基本概念¶

12.4.2 二分图判定 — 染色法¶

12.4.3 染色法代码¶

12.4.4 匈牙利算法（最大匹配）¶

12.4.5 图解匈牙利算法¶

12.4.6 匈牙利算法代码¶

12.4.7 复杂度分析¶

12.4.8 常见应用¶

12.5 网络流简介¶

12.5.1 基本概念¶

12.5.2 基本定理¶

12.5.3 Dinic 算法¶

12.5.4 代码实现¶

12.5.5 复杂度分析¶

12.5.6 竞赛中的网络流¶

12.6 树上技巧¶

12.6.1 树的直径¶

12.6.2 树直径代码¶

12.6.3 LCA — 倍增法¶

12.6.4 图解倍增¶

12.6.5 LCA 倍增代码¶

12.6.6 树链剖分简介¶

12.6.7 树链剖分代码框架¶

12.7 虚拟节点技巧¶

12.7.1 什么是虚拟节点¶

12.7.2 典型用法一：多源 BFS / 最短路¶

12.7.3 典型用法二：虚树¶

12.7.4 典型用法三：分层图最短路¶

12.7.5 虚拟节点技巧总结¶

综合练习题¶

Day 7 图论进阶（12 题）¶

Codeforces 题目¶

AtCoder 题目¶

洛谷题目¶

解题要点提示¶

学习建议¶

第十二章图论进阶¶