CSP-S 提高级课程中心 / 图结构与哈希 / 第19讲
CSP-S 提高级 · 图结构与哈希 · s4-01

常见图分类：稀疏图、偶图、欧拉图与 DAG

拿到一道图论题，先别急着写代码 —— 看清这张图属于哪一类，条件就可以像公式一样直接套用，很多题目的「做法」其实早被图的种类决定了。

4 类图与判定条件 3 个完整案例 2 处交互动画 6 大模块 12 道洛谷原题
本讲 · 第 19/52 讲常见图分类：稀疏图、偶图、欧拉图与DAG
模块 01

情景导航

先用一个真实的校园情境，让你感受到「同一张图，看的角度不同，能用的工具完全不同」。

故事科技节的三道难题

小林是学校信息社的社长，今年轮到他们社团承办校园科技节。开幕前一周，他桌上堆了三张图纸，每一张都让他头疼。

第一张图是「岗位分配表」：学校有 6 名志愿者，8 个展区岗位，每个志愿者只会应聘其中几类岗位。小林想安排「每个人恰好负责一个岗位、每个岗位恰好由一个人负责」，问最多能排满多少个岗位？指导老师看了一眼说：「你这就是在二分图里求最大匹配。」

第二张图是「巡展通道图」：科技节有若干展馆，展馆之间由走廊相连。小林希望设计一条巡视路线，让每一条走廊恰好走一次，最后回到出发点，这样每段路都能检查到又不会重复走冤枉路。老师又笑了：「典型的欧拉回路问题，看度数为奇数的是不是 0 个。」

第三张图是「筹备任务图」：搭建展台、印制海报、联系嘉宾、调试设备……任务之间有严格的先后依赖（海报没印好就没法布展）。小林想知道「最少要分几个阶段，才能把所有任务排完」。老师说：「把依赖画成有向图，若没有环，就能拓扑排序。」

三张图，三个问题，答案竟然都取决于图「长什么样」。小林这才明白：图论不是背模板，而是先给图做「体检」，再决定用什么药。

看图 → 分类 → 套条件 → 选算法，这才是提高组图论的正确打开方式。

💡 故事背后的算法思想

稀疏还是稠密决定「怎么存」：志愿者和岗位之间的边很少，属于稀疏图；如果用 n×n 的邻接矩阵存，绝大部分格子都是 0，白白浪费空间。反过来，若图本来就有 O(n²) 条边（如完全图），矩阵反而更快。

二分图决定「能不能匹配」：第一张图里「志愿者」和「岗位」是两个互不相交的集合，边只在集合之间，这正是二分图的定义。二分图有大量漂亮性质（最大匹配 = 最小点覆盖 = 最大独立集补集），这是普通图没有的。

欧拉图决定「能不能一笔画」：一笔画的存在性与「每个点的度数奇偶性」严格挂钩。奇度点个数只有 0、2 两种可能值，这是图论中少见的「充要条件如此干净」的定理。

DAG 决定「能不能按顺序推」：无环的有向图存在拓扑序，所有「拓扑序上从前往后推」的 DP 都能一趟搞定，复杂度 O(n+m)。一旦有环，这套逻辑立刻崩掉。

①生活类比
🕸️

渔网 vs 铁板 = 稀疏 vs 稠密

渔网孔多绳少，只需记「哪两个结连着」；铁板处处是面，用网格表记录更直观。

→ m 与 n² 的关系
⚽

球赛分组 = 二分图

红队与蓝队之间才比赛，同队队员之间从不对局，这就是「边只在两部分之间」。

→ 无奇环
✏️

一笔画图案 = 欧拉图

小时候画的星星能否一笔画完且不抬笔，取决于「奇点」有几个。

→ 奇度点 0 或 2 个
📚

先修课表 = DAG

「高数 → 线代 → 机器学习」这种依赖链不可能成环，否则永远毕不了业。

→ 拓扑序
②核心定义

稀疏图 (Sparse Graph)：当边数 m 远小于顶点数平方 n² （通常 m = O(n) 或 O(n log n)）时称稀疏图；反之 m 接近 n² 时称稠密图 (Dense Graph)。

二分图 / 偶图 (Bipartite Graph)：若顶点集 V 可以划分为两个互不相交的子集 L、R，使得图中每条边的两个端点分别属于 L 与 R，则称该图为二分图。

欧拉通路 (Euler Path)：经过图中每条边恰好一次的通路；若这条通路的起点与终点相同（首尾相接成回路），则称欧拉回路 (Euler Circuit)。含欧拉回路的图称为欧拉图。

有向无环图 (DAG, Directed Acyclic Graph)：不含任何有向环的有向图。DAG 一定存在拓扑序，是「阶段型 DP」最自然的载体。

📌 本讲核心知识地图

板块核心内容对应大纲
稀疏图m 与 n² 的关系、邻接矩阵↔邻接表选型稀疏图【5】
二分图（偶图）两侧划分、无奇环、染色法判定偶图【6】
欧拉图度数与连通性条件、Hierholzer 求路径欧拉图【6】
有向无环图拓扑序存在、DAG 上计数与 DP有向无环图【6】
判定技巧BFS/DFS 染色、度数统计、拓扑排序图的基本算法
③核心口诀
🔑 分类总纲

拿到图先做体检：边多边少选存法，两侧分明看奇环，奇点零二一笔画，无环方能拓扑排。

🔑 二分图

二分图等价于没有奇环；染色法一遍 DFS，颜色冲突即宣告失败。

🔑 欧拉图

无向图：连通 + 奇度点 0 个为回路、2 个为通路；有向图：连通 + 入度出度全相等为回路。

模块 02

知识探究

四类图逐一拆解：定义 → 判定条件 → 存储选型 → 完整代码 → 动画演示。

1稀疏图与稠密图 基础

图 G = (V, E)，|V| = n，|E| = m。无向图最多 C(n,2) = n(n−1)/2 条边，有向图最多 n(n−1) 条边。所谓「稀疏」「稠密」，说的就是 m 相对于 n² 处于什么量级。

1
🕸️
稀疏图

m ≈ O(n)，边数只是点数的几倍。如地铁线路图、社交关注关系。

2
🧱
稠密图

m ≈ O(n²)，边数接近上限。如完全图、竞赛积分表、小规模 Floyd。

3
⚖️
分界线

经验值：m 与 n² 同阶算稠密，m ≤ n log n 一定算稀疏。

存储方式空间复杂度判断 u→v 是否有边遍历 u 的所有邻居适用
邻接矩阵 g[n][n]O(n²)O(1)O(n)稠密图 / 需要 O(1) 查边
邻接表 vector<int> e[n]O(n+m)O(deg(u))O(deg(u))稀疏图 / 遍历为主
链式前向星O(n+m)O(deg(u))O(deg(u))大规模稀疏图 / 常数更小
边集数组O(m)O(m)O(m)Kruskal / 只需枚举所有边

📐 选型如何影响算法

n ≤ 500 时不假思索用矩阵：n² = 250000，矩阵完全放得下，Floyd 求全源最短路 O(n³) 也是这个量级的经典做法。

n ≤ 1e5 的稀疏图必须用邻接表：若强行开 g[100005][100005]，需要 4×10¹⁰ 个 int ≈ 160 GB，直接编译都过不了。

同一算法换存储，复杂度会变：堆优化 Dijkstra 用邻接表是 O(m log m)；若改成邻接矩阵「扫全行找最小」，就退化成 O(n² + m log m)，稀疏图上反而更慢。

判断稀疏的实战意义：读题时看「n 与 m 的数量级」——若题目给 n ≤ 1e5、m ≤ 2e5，说明是稀疏图；若给 n ≤ 500 却不给 m，暗示 m 可能很大，直接上矩阵。

🔑 选型口诀

点少边多用矩阵，点多边少挂链表；先看数据范围，再写存储结构。

▶ 存储选型模拟器（代入真实数据范围）
1读题第一眼：n ≤ 500，未给 m 上限 → 最坏 m ≈ n²/2 ≈ 125000 条边，属稠密图。
2估算矩阵空间：500×500×4B ≈ 1 MB，绰绰有余 → 直接开邻接矩阵，O(1) 查边还能顺手跑 Floyd。
3换一道题：n ≤ 1e5, m ≤ 2e5 → m 与 n 同阶，是稀疏图。
4估算矩阵空间：1e5 × 1e5 × 4B ≈ 40 GB，远超 256MB → 矩阵方案当场否决。
5改用邻接表：空间 O(n+m) ≈ 3×10⁵ 条表项，只有几 MB，遍历邻居也只花 O(deg)。
6结论固化：先算 n² 与 m 的量级，再决定存储；这一步在写任何图论算法之前完成。
两道题的数据范围就是两种答案 —— 选型不是偏好，是被空间与时间逼出来的必然。
2二分图（偶图）高频

二分图的核心是「两类对象、只跨类相连」。形式化地说：存在划分 V = L ∪ R，L ∩ R = ∅，使得每条边 (u, v) 都满足 u ∈ L 且 v ∈ R（或反之）。

L L L R R R 左侧集合内无边 · 右侧集合内无边
🎨 二染色 = 二分图
  1. 把 L 全部染成蓝色，R 全部染成粉色；
  2. 每条边的两个端点颜色必然不同；
  3. 反之，若一张图能被这样二染色，它一定是二分图。

关键定理：图 G 是二分图 ⟺ G 中不含长度为奇数的环（奇环）。

直观理解：沿着环走一圈回到起点，若环长为奇数，颜色会「翻」奇数次，起点被迫与自己异色 —— 矛盾。

🔍 染色法判定流程（BFS 版）

第1步：col[1..n] 初始化为 -1（未染色）。

第2步：对每个未染色的点 i，令 col[i] = 0 并入队（处理非连通图的关键）。

第3步：BFS 扩展，若邻点未染色则染成 1−col[u]；若已染色且 col[v] == col[u]，说明出现冲突 → 不是二分图。

复杂度：每个点每条边访问一次，O(n+m)。

易错点：只从一个点出发染色，非连通图会漏掉其余连通块，导致误判为二分图。

✅ 二分图（无奇环）

可以二染色；最大匹配可用匈牙利算法 O(nm)；最小点覆盖 = 最大匹配；最大独立集 = n − 最大匹配。

❌ 非二分图（含奇环）

三角形 K₃、五边形 C₅ 都是最小反例。染色必然冲突，上述所有匹配性质全部失效。

3欧拉图 高频

欧拉通路是「一笔画走遍所有边、每条边恰好一次」的路线；欧拉回路要求这条路线的首尾重合。注意：点可以重复经过，但每条边只能走一次。

图的类型欧拉回路存在条件欧拉通路存在条件
无向图所有非孤立点连通，且所有点度数为偶数连通，且恰有 0 个或 2 个奇度点（0 个时回路即通路）
有向图忽略方向后连通，且每个点 in[u] == out[u]连通，且恰有一个点 out−in = 1（起点）、一个点 in−out = 1（终点），其余相等

📐 为什么是「奇度点」？

想象你在一笔画过程中经过某个点：进来一次就必须出去一次，所以经过的边总是成对消耗的，该点的度数必然是偶数。

只有两种例外：起点（可以「先出去」不进来）和终点（可以「进来」不出去）。所以奇度点最多只能有 2 个，且这 2 个必须分别是起点和终点。

这就是为什么「奇度点 0 个 → 回路」：没有例外点，起点终点合一，形成闭环。

连通性为什么不能少：若图分成两个互不相连的部分，各自度数为偶数也无法一笔画跨过去。所以必须先判断「所有非孤立点在同一连通块」。

▶ 欧拉回路一笔画演示（Hierholzer）
1样例图：1—2、2—3、3—1 构成三角形，1—4、4—5、5—1 构成第二个三角形。所有点度数为 2（偶数），存在欧拉回路。
2从起点 1 出发，DFS 深入：走 1 → 2。
3在 2 号点继续走未访问的边：2 → 3，再从 3 走 3 → 1，回到起点 1。
4此时 1 号点还有未访问的边 1 → 4，继续 DFS：1 → 4 → 5 → 1。
5所有边都访问完，回溯时把点依次压入答案栈：得到 3,2,1,5,4,1（末尾补起点 1）。
6把栈中元素倒序输出：1 → 4 → 5 → 1 → 2 → 3 → 1，正是完整欧拉回路。
Hierholzer 的精髓：走不通就回溯，回溯时把点记下来，最后倒序输出。整个过程 O(n+m)。

⚡ Hierholzer 算法（求欧拉回路）

核心思想：从起点出发不停往前走，直到走不动；此时把当前点加入答案，退回上一个点继续找没走过的边。最后把答案数组倒序输出。

实现要点：用 multiset / 排序后的 vector + 指针删除，或链式前向星配合 used[] 标记，避免在 DFS 中 O(deg) 删除导致复杂度退化。

复杂度：每条边恰好被删除一次，O(m log m)（用 set）或 O(m)（用前向星）。

✅ 欧拉回路

起点 = 终点，所有奇度点为 0 个。可从一个点出发「绕圈再绕圈」把整张图走完。

⚠️ 欧拉通路（非回路）

起点与终点不同，恰有 2 个奇度点。此时算法必须指定从奇度点出发，否则会失败。

4有向无环图 DAG 核心

DAG 是「有方向但绕不回自己」的图。它最重要的性质是：一定存在拓扑序（把点排成一列，使所有边都从前往后指），因此所有「按阶段推状态」的 DP 都能在 DAG 上顺利执行。

1
🔗
依赖关系

任务 A 必须在 B 之前完成 → 连 A→B 的有向边。

2
📋
拓扑序存在

用 Kahn 算法不断取入度为 0 的点，取出 n 个即为 DAG。

3
📈
DP 天然阶段

按拓扑序推 f[v] += f[u]，前驱一定先算完。

C++Kahn 拓扑排序模板（同时判定是否成环）
int indeg[MAXN], topo[MAXN], cnt = 0;
queue<int> q;
for (int i = 1; i <= n; i++)
    if (indeg[i] == 0) q.push(i);   // 入度为 0 的点可以最先做
while (!q.empty()) {
    int u = q.front(); q.pop();
    topo[++cnt] = u;
    for (int v : e[u]) {
        if (--indeg[v] == 0) q.push(v);  // 前驱全部完成才入队
    }
}
// cnt == n 说明是 DAG；cnt < n 说明存在环

🔍 DAG 上的三类经典问题

① 拓扑排序：判断依赖是否合法、给任务排阶段。O(n+m)。

② DAG 最长路：按拓扑序做 DP，dp[v] = max(dp[v], dp[u] + w)。因为无环，不会被「循环更新」困住，O(n+m)，比 SPFA 快且稳定。

③ DAG 路径计数：f[v] += f[u]，从源点推。若要求「到达某点的路径条数 mod p」，直接加即可。

反例警示：一旦图里有环，上述 DP 会无限更新（如 1→2→1 加权重），必须先用 Tarjan 缩点把环压成一个点，转成 DAG 再 DP —— 这正是 s4-02 与 s5-15 要解决的问题。

STEP 1统计入度
STEP 2入队零度点
STEP 3弹出并松弛
STEP 4新零度点入队
STEP 5检查是否成环
鼠标悬停节点查看说明
案例案例1：染色法判定二分图 经典

题目：给定一张 n 个点 m 条边的无向图（可能不连通），判断它是否为二分图。n, m ≤ 2×10⁵。

🔍 详细分析过程

第1步：识别模型 —— 「能否把所有点分成两类，使每条边都跨类」= 二分图判定 = 二染色。

第2步：遍历方式 —— 用 BFS 逐层染色。起点染 0，邻居染 1，再下一层染 0……

第3步：冲突检测 —— 若碰到已染色的邻居且颜色与当前点相同，立刻输出 "No"。

第4步：非连通处理 —— 外层 for 循环确保每个未染色的点都作为新连通块的起点（最容易漏的一步）。

C++染色法判定二分图 — 完整代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
vector<int> e[MAXN];       // 邻接表存稀疏图
int col[MAXN];                // -1 未染色, 0/1 两种颜色

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);    // 无向图双向加边
    }
    memset(col, -1, sizeof(col));
    for (int s = 1; s <= n; s++) {          // 枚举每个连通块
        if (col[s] != -1) continue;
        col[s] = 0;
        queue<int> q; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : e[u]) {
                if (col[v] == -1) {              // 未染色：染反色
                    col[v] = col[u] ^ 1;
                    q.push(v);
                } else if (col[v] == col[u]) {   // 冲突：出现奇环
                    cout << "No" << endl;
                    return 0;
                }
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}
运行结果
测试1（偶环 4 个点）:
输入: 4 4
      1 2
      2 3
      3 4
      4 1
输出: Yes

测试2（奇环 3 个点构成三角形）:
输入: 3 3
      1 2
      2 3
      3 1
输出: No
🔍 代码逐段解析 · 染色法判二分图
1建图（第 6~10 行）：n, m 可达 2×10⁵，属稀疏图，用 vector<int> e[] 邻接表；无向图每条边 push_back 两次。
2memset(col, -1, sizeof(col))：-1 表示「未染色」。注意 memset 按字节赋值，-1（0xFF）恰好可整型填充。
3外层 for (s = 1..n)：枚举每个连通块的起点，col[s] != -1 就 continue 跳过已染色块 —— 非连通图的命门。
4BFS 主循环：弹出队首 u，扫它的所有邻居 v。
5col[v] == -1 分支：v 未染色，染成 col[u]^1（异或 1 即取反色），并 v 入队。
6col[v] == col[u] 分支：已染色且同色 → 相邻同色，说明存在奇环，输出 No 直接 return。
7全部通过：所有连通块染完无冲突，输出 Yes。
8易错点：① 忘记外层枚举起点，非连通图漏判；② 邻居已染色时只在「同色」时处理，切勿把「异色」也当冲突。
每个点入队一次、每条边被扫两次（无向），复杂度 O(n+m)。

💡 为什么「无奇环」和「可二染色」等价？

方向一（二染色 ⇒ 无奇环）：沿任意环走一圈，颜色必然交替变化。走偶数步颜色回到原色，走奇数步颜色变成反色。若环长为奇数，回到起点时颜色与起点自身颜色矛盾 → 不存在奇环。

方向二（无奇环 ⇒ 二染色）：对每个连通块任选起点染 0，按 BFS 层数染色。若染色过程中出现冲突，说明找到了一条「同色相邻」路径，把它和 BFS 树路径拼起来恰好构成奇环 —— 与假设矛盾。

所以这两个条件互为充要，考试中可直接引用。

案例案例2：判断欧拉回路是否存在 NOIP

题目：给定一张无向图（可能不连通），判断它是否存在欧拉回路；若存在，输出 "Euler Circuit"，否则输出 "None"。

🔍 详细分析过程

第1步：度数条件 —— 统计所有点的度数，只要有任意一个点度数为奇数，直接判否。

第2步：连通性条件 —— 从任意一个有边的点出发 BFS/DFS，检查所有度数 > 0 的点是否都被访问到。

第3步：边界情况 —— 图里一条边都没有（m = 0）时应视为不存在有效欧拉回路；孤立点不影响判定，必须跳过。

第4步：先判度数再判连通 —— 度数检查 O(n)，连通检查 O(n+m)，整体 O(n+m)。

C++判断无向图欧拉回路 — 完整代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
vector<int> e[MAXN];
int deg[MAXN];
bool vis[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    if (m == 0) { cout << "None" << endl; return 0; }
    int st = -1;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        e[u].push_back(v); e[v].push_back(u);
        deg[u]++; deg[v]++;
        st = u;                       // 记一个有边的起点
    }
    // 条件一：所有非孤立点度数为偶数
    for (int i = 1; i <= n; i++)
        if (deg[i] % 2 != 0) { cout << "None" << endl; return 0; }
    // 条件二：从 st 出发能到达所有 deg > 0 的点
    queue<int> q; q.push(st); vis[st] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : e[u])
            if (!vis[v]) { vis[v] = true; q.push(v); }
    }
    for (int i = 1; i <= n; i++)
        if (deg[i] > 0 && !vis[i]) { cout << "None" << endl; return 0; }
    cout << "Euler Circuit" << endl;
    return 0;
}
运行结果
测试1（三角形，每个点度数 2）:
输入: 3 3
      1 2
      2 3
      3 1
输出: Euler Circuit

测试2（路径 1-2-3，点 1 和 3 度数为 1）:
输入: 3 2
      1 2
      2 3
输出: None

测试3（两个不相连的三角形）:
输入: 6 6
      1 2 / 2 3 / 3 1
      4 5 / 5 6 / 6 4
输出: None    ← 度数全偶，但不连通
🔍 代码逐段解析 · 欧拉回路判定
1m == 0 特判：一条边都没有时谈不上「走遍所有边」，输出 None（本讲题意约定）。
2读边同时 deg[u]++、deg[v]++：无向边对两端各贡献 1 度；st = u 顺手记一个「有边的点」作 BFS 起点。
3条件一（第 14~15 行）：扫一遍 1..n，任何 deg[i] % 2 != 0 立即输出 None —— 度数检查只要 O(n)。
4条件二 BFS：从 st 出发标记 vis，看能否覆盖所有有边点。
5收尾检查：deg[i] > 0 && !vis[i] 说明第 i 个有边点孤立于 st 所在连通块之外 → None。
6易错点：① 连通性检查若漏写 deg[i] > 0，孤立点会被误判成「不连通」；② 先判度数再判连通，能把一半情况提前剪掉。
整体两遍线性扫描，O(n+m)。
案例案例3：DAG 上的路径计数 进阶

题目：给定一个 n 个点 m 条边的 DAG 和起点 S、终点 T，求从 S 到 T 的不同路径条数（对 10⁹+7 取模）。n ≤ 10⁵，m ≤ 2×10⁵。

🔍 详细分析过程

第1步：识别模型 —— 「路径计数」天然满足加法原理：到 v 的路径数 = 所有前驱 u 的路径数之和。而 DAG 保证前驱一定在拓扑序前面，可以顺序递推。

第2步：状态定义 —— f[v] 表示「从 S 到 v 的路径条数」。初值 f[S] = 1，其余为 0。

第3步：转移方程 —— 按拓扑序处理 u，对每条边 u→v 执行 f[v] = (f[v] + f[u]) % MOD。

第4步：为什么不能直接 DFS 记忆化 —— 记忆化搜索本身也能做（DAG 上无后效性），但拓扑序写法常数更小、不爆栈，处理 10⁵ 规模更稳。

第5步：注意点 —— 只有从 S 可达的点才会被赋到非零值，因为队列推送时只推送回溯可达的点；若用拓扑序整体扫，需要判断 f[u] 是否为 0。

C++DAG 路径计数 — 完整代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const long long MOD = 1000000007;
vector<int> e[MAXN];
int indeg[MAXN], topo[MAXN], cnt;
long long f[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, S, T; cin >> n >> m >> S >> T;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        e[u].push_back(v);
        indeg[v]++;
    }
    queue<int> q;
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) q.push(i);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        topo[++cnt] = u;
        for (int v : e[u])
            if (--indeg[v] == 0) q.push(v);
    }
    f[S] = 1;
    for (int i = 1; i <= cnt; i++) {
        int u = topo[i];
        if (f[u] == 0) continue;          // S 不可达的点跳过
        for (int v : e[u])
            f[v] = (f[v] + f[u]) % MOD;
    }
    cout << f[T] % MOD << endl;
    return 0;
}
运行结果
输入: 6 7 1 6
      1 2
      1 3
      2 4
      3 4
      4 5
      2 5
      5 6
输出: 3
🔍 代码逐段解析 · DAG 路径计数
1读边 + indeg[v]++（第 8~11 行）：有向边只加一次邻接；同步统计入度供 Kahn 使用。
2入队所有 indeg==0 的点：它们没有前置依赖，是拓扑序的开头。
3Kahn 主循环：出队 u 记入 topo[++cnt]，每条出边 --indeg[v] == 0 时把 v 入队。
4f[S] = 1：边界 —— 「从 S 到 S」有一条空路径；其余 f 初值 0。
5if (f[u] == 0) continue：S 不可达的点跳过，防止给不可达点「凭空造路」。
6f[v] = (f[v] + f[u]) % MOD：加法原理，沿拓扑序把 u 的方案数推给每个后继 v。
7易错点：① f 是 long long，f[u]+f[u] 相加前各自已取模不会溢出，但若边权带系数需先取模；② 忘记判可达导致多算。
拓扑 O(n+m) + DP O(n+m)，样例中 f[4]=2、f[5]=3、f[6]=3，与正文手算一致。

💡 三条路径分别是哪些？

① 1 → 2 → 4 → 5 → 6

② 1 → 2 → 5 → 6

③ 1 → 3 → 4 → 5 → 6

可以看到 f[4] = f[2] + f[3] = 1 + 1 = 2（两条到 4 的路），f[5] = f[2] + f[4] = 1 + 2 = 3，f[6] = f[5] = 3。这就是「拓扑序上从前往后加」的威力。

模块 03

实践应用

三道完整题目，从「识别图类」到「写出代码」全过程训练。

题1志愿服务分组（二分图染色）
题 1图分类 · 二分图

科技节需要把 n 名志愿者分成「上午组」和「下午组」。给出 m 组「不能分在同一组」的限制关系，问是否存在合规的分组方案。

输入格式：第一行两个整数 n, m（1 ≤ n ≤ 10⁵，0 ≤ m ≤ 2×10⁵）。接下来 m 行，每行两个整数 u, v，表示第 u 名与第 v 名志愿者不能在同一组。

输出格式：若存在合法分组输出 Yes，否则输出 No。

输入样例：

输入
4 4
1 2
2 3
3 4
4 1

输出样例：

输出
Yes

数据范围：时间限制 1s，空间限制 256MB。

🔍 题目分析

方法一（暴力枚举）不可行 —— 枚举 2ⁿ 种分组方案逐一检查。n = 10⁵ 时完全爆炸，只能拿 n ≤ 20 的部分分。

方法二（图染色）正解 —— 「不能同组」就是「必须异色」，这正是二分图染色。把每位志愿者看作点，限制关系看作边，判定图是否二分图即可。O(n+m) 通过。

关键转换：这类「分成两类、某些元素必须分开」的题，几乎都可以直接翻译成二分图染色。

C++志愿服务分组 — 完整代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> e[MAXN];
int col[MAXN];

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);
    }
    memset(col, -1, sizeof(col));
    for (int s = 1; s <= n; s++) {
        if (col[s] != -1) continue;
        col[s] = 0;
        queue<int> q; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : e[u]) {
                if (col[v] == -1) { col[v] = col[u] ^ 1; q.push(v); }
                else if (col[v] == col[u]) { cout << "No" << endl; return 0; }
            }
        }
    }
    cout << "Yes" << endl;
    return 0;
}
运行结果
输入: 4 4 / 1 2 / 2 3 / 3 4 / 4 1
输出: Yes

（改为 1 2 / 2 3 / 3 1 时）
输出: No

🔍 代码逐段解析 · 志愿服务分组

第 6~9 行 —— 建图：志愿者为点，「不能同组」关系为边。m ≤ 2×10⁵ 属稀疏图，邻接表存储。

第 11 行 —— memset(col, -1, ...) 全部标记为未染色。

第 12~17 行 —— 外层枚举每个连通块起点（本题不保证连通），内层 BFS 染反色 col[u]^1。

第 19 行 —— 冲突判定：col[v] == col[u] 即两个「不能同组」的人被分进了同一组，输出 No。

易错点 —— n 可达 10⁵ 而本题保证连通时也务必保留外层循环写法（模板一致性）；col[v] = col[u] ^ 1 别写成 +1，否则 1 号颜色会溢出到 2。

💡 拓展思考

如果题目改为「求最多能把多少人安排到上午组」，就不只是判定，而要在二分图中求「最大独立集」。由 König 定理，二分图最大独立集 = n − 最大匹配，这就进入了「二分图匹配」的领域。

题2一笔画游园路线（欧拉路径）
题 2欧拉图 · 度数判定

给定一张无向图，判断是否存在欧拉通路（可以不在起点结束）；若存在，输出两个可作为起点的点编号（或同一个点）。

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

输出格式：第一行输出 Yes 或 No；若为 Yes，第二行输出可选的起点编号，若有多个输出最小的一个。

输入样例：

输入
4 3
1 2
2 3
3 4

输出样例：

输出
Yes
1

数据范围：1s / 256MB。

🔍 题目分析

方法一（枚举起点 + 暴力 DFS）会超时 —— 对每个点尝试 DFS 找一条经过所有边一次的路径，最坏 O(n·m)，n = 10⁵ 时必 TLE。

方法二（度数 + 连通性判定）正解 —— 利用定理：连通图中奇度点个数为 0 → 任意点可作起点；为 2 → 必须从这两个奇度点之一出发；其它情况无欧拉通路。O(n+m)。

注意：判定前要先忽略孤立点（度数为 0 的点）做连通性检查，否则会把「一个三角形 + 一个孤立点」误判为不连通。

C++欧拉通路判定 — 完整代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> e[MAXN];
int deg[MAXN];
bool vis[MAXN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
    if (m == 0) { cout << "Yes" << endl << 1 << endl; return 0; }
    int st = -1;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        e[u].push_back(v); e[v].push_back(u);
        deg[u]++; deg[v]++; st = u;
    }
    int odd = 0, firstOdd = -1;
    for (int i = 1; i <= n; i++)
        if (deg[i] % 2) { odd++; if (firstOdd == -1) firstOdd = i; }
    if (odd != 0 && odd != 2) { cout << "No" << endl; return 0; }
    queue<int> q; q.push(st); vis[st] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : e[u]) if (!vis[v]) { vis[v] = true; q.push(v); }
    }
    for (int i = 1; i <= n; i++)
        if (deg[i] > 0 && !vis[i]) { cout << "No" << endl; return 0; }
    cout << "Yes" << endl;
    if (odd == 2) {
        int mn = 1e9;
        for (int i = 1; i <= n; i++)
            if (deg[i] % 2) mn = min(mn, i);
        cout << mn << endl;            // 必须从奇度点出发
    } else {
        for (int i = 1; i <= n; i++)
            if (deg[i] > 0) { cout << i << endl; break; }  // 任意有边点均可
    }
    return 0;
}
运行结果
输入: 4 3 / 1 2 / 2 3 / 3 4
输出: Yes
      1        （点 1、4 是奇度点，输出较小的 1）

输入: 3 3 / 1 2 / 2 3 / 3 1
输出: Yes
      1        （全偶度，输出最小有边点 1）

🔍 代码逐段解析 · 欧拉通路判定

第 8 行 —— m == 0 特判：无边时输出 Yes 和 1（空路径从任意点出发，按题意取最小编号）。

第 10~14 行 —— 读边、累计度数、记录有边点 st。

第 15~18 行 —— 统计奇度点个数 odd 与最小编号 firstOdd；odd 不为 0 且不为 2 直接 No（握手定理保证 odd 必为偶数，不会出现 1、3 等值）。

第 19~24 行 —— 从 st BFS 检查「所有 deg>0 的点连通」，忽略孤立点。

第 26~33 行 —— 输出起点：odd==2 时必须从奇度点出发（取较小编号）；odd==0 时任意有边点皆可（取最小编号）。

易错点 —— ① odd==2 时若从偶度点出发，这条路走不完所有边；② 输出「最小的奇度点」而非 firstOdd 之外的另一个。

题3课程先修链（DAG 拓扑排序）
题 3DAG · 拓扑排序判定

给定 n 门课程和 m 条先修关系 (u, v)（表示 u 必须在 v 之前修），判断能否安排一个合法的修读顺序；若能，输出字典序最小的方案。

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

输出格式：若可以，输出 n 个整数表示修读顺序；否则输出 Impossible。

输入样例：

输入
5 4
1 2
1 3
2 4
3 4

输出样例：

输出
1 2 3 4 5

数据范围：1s / 256MB。

🔍 题目分析

方法一（普通队列 Kahn）基础 —— 用普通 queue，能判环、能输出某个合法拓扑序，但不保证字典序最小。

方法二（优先队列 Kahn）本题正解 —— 把 queue 换成 priority_queue<int, vector<int>, greater<int>>（小根堆），每次取出编号最小的可用点，得到的拓扑序字典序最小。复杂度 O((n+m) log n)。

结论：只要题目出现「字典序最小 / 编号最小优先」，Kahn 算法里的队列就必须换成优先队列。

C++课程先修链 — 完整代码
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
vector<int> e[MAXN];
int indeg[MAXN];

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);
        indeg[v]++;
    }
    priority_queue<int, vector<int>, greater<int>> pq;   // 小根堆 → 字典序最小
    for (int i = 1; i <= n; i++)
        if (indeg[i] == 0) pq.push(i);
    vector<int> ans;
    while (!pq.empty()) {
        int u = pq.top(); pq.pop();
        ans.push_back(u);
        for (int v : e[u])
            if (--indeg[v] == 0) pq.push(v);
    }
    if ((int)ans.size() != n) { cout << "Impossible" << endl; return 0; }
    for (int i = 0; i < n; i++) cout << ans[i] << " \n"[i == n - 1];
    return 0;
}
运行结果
输入: 5 4 / 1 2 / 1 3 / 2 4 / 3 4
输出: 1 2 3 4 5

输入（成环）: 3 3 / 1 2 / 2 3 / 3 1
输出: Impossible
🔍 代码逐段解析 · 字典序最小拓扑排序
1建图 + indeg[v]++（第 6~10 行）：u 必须先于 v，连有向边 u→v。
2priority_queue<int, vector<int>, greater<int>>：本题主角的灵魂 —— greater 使其为小根堆，每次弹出最小可用点。
3入队所有入度为 0 的点：堆里是「当前所有可立即修读」的课程。
4主循环：取堆顶最小编号 u，追加到 ans，对其每个后继 v 减入度，减到 0 就入堆。
5ans.size() != n → Impossible：有环时环上的点入度永远减不到 0，无法全部取出。
6" \n"[i == n-1]：行内空格分隔、行末换行的小技巧，避免行尾多余空格。
7易错点：① 用大根堆（默认 priority_queue<int>）得不到字典序最小；② 复杂度是 O((n+m) log n)，不是 O(n+m)。
样例执行顺序：堆 {1,5}→取1→堆{2,3,5}→取2→堆{3,4,5}→取3→取4→取5，输出 1 2 3 4 5。
模块 04

总结提升

①核心要点与万能模板
图类判定条件典型算法复杂度
稀疏 / 稠密m 与 n² 的量级比较邻接表 / 邻接矩阵选型O(n+m) / O(n²)
二分图可二染色 ⟺ 无奇环BFS/DFS 染色O(n+m)
欧拉回路连通 + 所有点度数为偶HierholzerO(m log m)
欧拉通路连通 + 恰有 0 或 2 个奇度点从奇度点出发 HierholzerO(m log m)
DAG可用拓扑排序取出全部 n 个点Kahn（队列 / 优先队列）O(n+m)

万能代码模板：一次遍历同时完成「度数统计 + 连通性 + 环检测」

C++图分类通用检查模板
// ---- 读入阶段：同时建立邻接表与度数 ----
for (int i = 1; i <= m; i++) {
    int u, v; cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);      // 有向图只保留这一行
    deg[u]++; deg[v]++;     // 有向图区分 indeg / outdeg
}

// ---- 检查 1：度数条件（欧拉）----
int odd = 0;
for (int i = 1; i <= n; i++) if (deg[i] % 2) odd++;

// ---- 检查 2：连通性（忽略孤立点）----
bool ok = true;
for (int i = 1; i <= n; i++)
    if (deg[i] > 0 && !vis[i]) { ok = false; break; }

// ---- 检查 3：二分图染色 ----
for (int s = 1; s <= n; s++) {
    if (col[s] != -1) continue;
    col[s] = 0; q.push(s);
    while (!q.empty()) { /* 染反色，遇冲突即失败 */ }
}

// ---- 检查 4：DAG 判定（Kahn）----
// cnt == n 则无环，否则存在环

🔍 代码逐段解析 · 图分类通用检查模板

读入阶段 —— 一趟读边同时完成三件事：建邻接表、累计度数（无向 deg，有向拆 indeg/outdeg）、记录有边点。这一步是后续所有检查的公共地基。

检查 1（欧拉度数条件） —— 只数 deg[i] % 2，O(n)；有向图要改成比较 indeg 与 outdeg 是否全相等。

检查 2（连通性） —— 检查对象是「deg > 0 且 !vis[i]」的点，孤立点天然豁免；vis 需先从任一有边点 BFS 得到。

检查 3（二分染色） —— 外层枚举连通块起点 + 内层 BFS 染反色，冲突即失败；骨架与案例1完全一致。

检查 4（DAG 判定） —— Kahn 出队计数 cnt 与 n 比较，一行判定有无环。

易错点 —— 四个检查各自独立，考场上按题目要求「点菜」使用即可，不要全跑一遍浪费时间；度数数组在有向图场景务必拆成两个。

②拓展案例

拓展1：二分图最大匹配（匈牙利算法思想）

💡 思路：为左侧每个点尝试找匹配。若它想连的右侧点已被占用，就尝试让占用者「让位」——递归地给占用者找别的点。这就是「增广路」思想。

复杂度：O(L · m)，L 为左侧点数。对 n ≤ 2000 的图完全够用。

C++匈牙利算法求二分图最大匹配
const int MAXN = 505;
vector<int> e[MAXN];
int match[MAXN];       // match[v] = 右侧点 v 匹配的左侧点
bool used[MAXN];

bool dfs(int u) {
    for (int v : e[u]) {
        if (used[v]) continue;
        used[v] = true;                       // 本轮尝试中不再访问 v
        if (match[v] == 0 || dfs(match[v])) {   // v 空闲 或 原配能让位
            match[v] = u;
            return true;
        }
    }
    return false;
}
// 主函数：对每个 u 清空 used 后 dfs(u)，成功则 ans++
运行结果
输入: 4 4 6
      1 1 / 1 2 / 2 2 / 2 3 / 3 3 / 4 4
输出: 4
（左 1→右 1，左 2→右 2，左 3→右 3，左 4→右 4）

拓展2：有向图欧拉路径 + 字典序最小（Hierholzer 实战）

💡 思路：把每个点的出边排序（或塞进 multiset），DFS 时永远走最小的那条，回溯时记录点，最后倒序输出。这样既保证正确性，又保证字典序最小。

复杂度：排序 O(m log m)，DFS O(m)。

C++Hierholzer 求字典序最小欧拉路径
vector<int> e[MAXN];
int indeg[MAXN], outdeg[MAXN];
vector<int> path;

void dfs(int u) {
    while (!e[u].empty()) {
        int v = e[u].back(); e[u].pop_back();   // 取最小出边（预先降序排序）
        dfs(v);
    }
    path.push_back(u);                          // 回溯时记录
}
// 输出：reverse(path.begin(), path.end())
运行结果
输入: 4 4
      1 2 / 2 3 / 3 4 / 4 1
输出: 1 2 3 4 1

拓展3：DAG 最长路（不用 SPFA）

💡 思路：拓扑序保证前驱先被处理，直接 dp[v] = max(dp[v], dp[u] + w) 一遍即可。相比 SPFA 的 O(km) 最坏情况，这个方法稳定 O(n+m)。

注意：dp 初值设为 −∞，只有能由源点到达的点才可更新，否则负权图会出错。

C++DAG 最长路
const long long NEG = -(1LL << 60);
long long dp[MAXN];
for (int i = 1; i <= n; i++) dp[i] = NEG;
dp[S] = 0;
for (int i = 1; i <= cnt; i++) {          // cnt 为拓扑序长度
    int u = topo[i];
    if (dp[u] == NEG) continue;
    for (auto [v, w] : e[u])
        dp[v] = max(dp[v], dp[u] + w);
}
运行结果
输入: 4 5  (S=1, T=4)
      1 2 3 / 1 3 1 / 2 4 2 / 3 4 5 / 2 3 1
dp = [-inf, 0, 3, 4, 9]
输出（最长路 1→2→3→4）: 9
③思考与启发

思考1：为什么二分图的性质这么「好」？

查看参考解答

二分图的结构限制极强：所有边都跨类，因此可以把它看成「两层结构」。最大匹配可以用增广路刻画，而 König 定理进一步说明「最大匹配 = 最小点覆盖」，把匹配问题转化成顶点覆盖问题。这类等价关系在一般图上全部不成立（一般图最大匹配需要带花树，复杂度高出许多）。

启示：结构越特殊，可用的定理越多。拿到题目先判断图的特殊性（二分、树、DAG、平面图），往往比直接套通用算法更有效。

思考2：为什么「所有点度数为偶数」不能保证有欧拉回路？

查看参考解答

反例：两个互不相连的三角形，每个点度数都是 2（偶数），但无法从第一个三角形走到第二个。所以连通性条件不可缺少。

更精细的说法是「所有非孤立点属于同一个连通块」。孤立点（度数为 0）可以任意存在，不影响欧拉回路的存在性。

考试中写判定函数时，务必写上「忽略度数为 0 的点」这一句，否则会被孤立点坑掉。

思考3：DAG 上的 DP 和一般图上的 DP，本质差别在哪？

查看参考解答

DP 能成立的前提是「无后效性」—— 状态之间可以排出一个顺序，使得每个状态只依赖排在自己前面的状态。

DAG 的拓扑序天然提供了这个顺序，所以「按拓扑序推一遍」就等价于「按 DP 阶段推一遍」。而一般有向图若有环，环上的状态互相依赖，无法排出合法顺序，DP 就失效了。

解决办法是缩点：用 Tarjan 把每个强连通分量压成一个点，得到 DAG，再在 DAG 上做 DP。这就是「SCC + 缩点 + DAG DP」这一套组合拳的来历。

模块 05

学习检测

先找错，再背口诀 —— 把易错点消灭在考试之前。

⚡高频错误诊断
易错1

非连通图只染色一个连通块

❌ 错误
只从 1 号点 BFS 一次就输出结果，其余连通块根本没检查。
✅ 正确
外层 for (int s = 1; s <= n; s++)，对每个未染色的点启动一次新的 BFS。
口诀：染色要扫全部点，未染色的都要当新起点！
易错2

绕行 deg[i]==0 的孤立点

❌ 错误
连通性检查写成 for (i=1..n) if (!vis[i]) 失败，图里有孤立点时误判为不连通。
✅ 正确
写成 if (deg[i] > 0 && !vis[i])，只检查「有边的点」是否都在同一连通块。
口诀：连通性检查记住一句 —— 只数有边的点！
易错3

有向图欧拉条件写成无向图版本

❌ 错误
有向图用「deg[u] 为偶数」判欧拉回路，把入度与出度混在一起算。
✅ 正确
有向图必须分别统计 indeg 与 outdeg，回路条件是 indeg[u] == outdeg[u] 对所有点成立。
口诀：无向看度数和，有向看入出相等！
易错4

稀疏图开邻接矩阵

❌ 错误
n = 10⁵ 却写 int g[100005][100005]，需要约 160 GB，编译或运行直接崩掉。
✅ 正确
稀疏图用 vector<int> e[MAXN] 或链式前向星，空间 O(n+m) 只有几 MB。
口诀：数据范围先看清，点多边少挂链表！
易错5

DAG 路径计数忘记判可达

❌ 错误
拓扑序推 f 时不做判断，导致 S 不可达的点也被赋上值，或答案错误。
✅ 正确
初值 f[S] = 1 其余为 0，转移前写 if (f[u] == 0) continue; 跳过不可达点。
口诀：计数先看可达性，f 为 0 的点直接跳！
📋速查表
判定目标核心条件实现要点
是否稀疏m 与 n² 量级比较m ≤ n log n 用邻接表；n ≤ 500 用矩阵
是否二分图可二染色col[v] = col[u]^1，冲突即失败
无向欧拉回路连通 + 全偶度先判度数，再判非孤立点连通
无向欧拉通路连通 + 奇度点 ∈ {0, 2}2 个奇度点时从其一出发
有向欧拉回路连通 + indeg 全等于 outdeg忽略方向判连通
是否 DAGKahn 能取出 n 个点cnt == n 即为 DAG
字典序最小拓扑序每次取最小可用点queue 换 priority_queue
📌笔记卡
必记概念
  • 二分图 ⟺ 无奇环
  • 欧拉回路：连通 + 全偶度
  • 欧拉通路：连通 + 奇度点 0 或 2
  • DAG：存在拓扑序
必背模板
  • BFS 二染色（判二分图）
  • 度数统计 + 连通性检查（判欧拉）
  • Kahn 拓扑排序（判 DAG、排任务）
  • Hierholzer（求欧拉路径）
考场提醒
  • 非连通图必须扫所有连通块
  • 孤立点不算「不连通」
  • 有向图入出度分开统计
  • n ≥ 1e5 别开矩阵
课后练习

分层练习作业

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

🟢 A组 · 基础（4题）

A1判断题

下列说法是否正确：① 有 5 个奇数度点的连通图一定存在欧拉通路；② K₃ 是二分图；③ DAG 中一定存在入度为 0 的点。

查看参考答案

① 错误。欧拉通路要求奇度点个数为 0 或 2，5 个奇度点无法一笔画。

② 错误。K₃ 是三角形，含长度为 3 的奇环，不是二分图。

③ 正确。若所有点入度都 ≥ 1，从任一点出发沿入边反向前走一定能回到已访问点（有限图鸽巢原理），从而形成有向环，矛盾于 DAG。

易错：把「奇度点 5 个」记成「奇数个」——条件只认 0 或 2，不是奇偶。

A2编程题

输入 n、m 和 m 条无向边，统计奇度点个数并输出。

查看参考答案
#include <bits/stdc++.h>
using namespace std;
int deg[100005];
int main() {
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; deg[u]++; deg[v]++; }
    int odd = 0;
    for (int i = 1; i <= n; i++) if (deg[i] % 2) odd++;
    cout << odd << endl;
}

思路：无向图每条边对两个端点的度数各贡献 1，读边时直接累加即可，O(n+m)。

逐段解析：第 3 行读入；第 4 行读每条边并对两端 deg 各加 1（O(1)/条）；第 5~6 行扫 1..n 统计 deg 为奇数的点的个数；第 7 行输出。易错：循环变量从 1 扫到 n 而不是 m，别把「点数」和「边数」搞混。

易错：有自环时一个自环使度数 +2；重边要算两次。本题无自环，但改成有向图时要分开统计入度和出度。

A3编程题

判断给定的无向图是否为二分图（输入保证连通）。

查看参考答案
#include <bits/stdc++.h>
using namespace std;
vector<int> e[100005];
int col[100005];
int main() {
    ios::sync_with_stdio(0);
    int n, m; 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); }
    memset(col, -1, sizeof(col));
    queue<int> q; q.push(1); col[1] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : e[u]) {
            if (col[v] == -1) { col[v] = col[u] ^ 1; q.push(v); }
            else if (col[v] == col[u]) { cout << "No"; return 0; }
        }
    }
    cout << "Yes";
}

逐段解析：第 5~6 行建邻接表；第 7 行 memset 未染色；第 8 行起点 1 染 0 入队（题目保证连通，无需外层枚举）；第 9~14 行 BFS：未染则染反色 col[u]^1 入队，已染且同色 col[v]==col[u] 输出 No 返回；第 15 行无冲突输出 Yes。

思路：BFS 逐层染色，冲突即为奇环。

易错：题目说了「保证连通」，但如果改成不保证连通，必须加外层循环枚举所有连通块。

A4选择题

一个有 n 个顶点、m 条边的无向图，若 m = n − 1 且连通，则该图一定是（ ）A. 二分图 B. 欧拉图 C. DAG D. 完全图

查看参考答案

答案：A。连通且 m = n − 1 的无向图是一棵树，树不含任何环，自然不含奇环，所以一定是二分图。

B 错：树的叶子度数为 1（奇数），一般不满足全偶度条件。

C 错：DAG 是「有向无环图」，本题是无向图，概念不适用。

D 错：完全图 Kₙ 有 n(n−1)/2 条边，仅 n = 2 时与 n−1 相等。

🟡 B组 · 提高（4题）

B1欧拉路径

给定有向图，判断是否存在欧拉路径；若存在，输出字典序最小的一条。

查看参考答案

思路：① 统计 indeg / outdeg；② 找出可能的起点（outdeg−indeg = 1 的点；全相等时任选）；③ Hierholzer 走完所有边，边走边删；④ 倒序输出。

vector<int> e[100005];
int in_[100005], out_[100005];
vector<int> path, stk;
void dfs(int u) {
    while (!e[u].empty()) { int v = e[u].back(); e[u].pop_back(); dfs(v); }
    path.push_back(u);
}
// 主函数：对每个点的出边降序排序，再 reverse 后 pop_back 才能取最小值

易错：出边排序方向搞反（想取最小却弹出最大）；或起点选错，导致路径长度不足 m+1。

B2DAG 最长路

给定 DAG 和起点 S，求 S 到每个点的最长路径长度。

查看参考答案

思路：拓扑排序后按序 DP，dp[v] = max(dp[v], dp[u] + w)。复杂度 O(n+m)，比 SPFA 稳定。

for (int i = 1; i <= cnt; i++) {
    int u = topo[i];
    if (dp[u] == NEG) continue;
    for (auto &pr : e[u]) {
        int v = pr.first, w = pr.second;
        dp[v] = max(dp[v], dp[u] + w);
    }
}

易错：dp 初值设为 0 而非 −∞，负权边会被「跳过」；或忘记 if (dp[u] == NEG) continue;，让不可达点参与松弛。

B3二分图计数

给定二分图，求两侧集合的点数之差的最小值（即最优划分）。

查看参考答案

关键观察：二分图的划分在每个连通块内是唯一的（交换两侧颜色等价）。因此对每个连通块独立统计「黑色数 − 白色数」，再用背包思想把差值凑到最小绝对值。

// 对每个连通块 BFS，得到 black[i] 与 white[i]
// 令 d[i] = black[i] - white[i]（可正可负）
// 用 bitset 或 bool 背包求解最接近 0 的绝对值
bitset<200005> f;
f[100000] = 1;              // 偏移量防止负数下标
for (int i = 1; i <= blocks; i++) {
    int di = abs(d[i]);              // 位移量必须非负，d[i] 可正可负
    f = (f << di) | (f >> di);       // 两种取法：同色或翻转颜色
}
for (int k = 0; k <= n; k++)
    if (f[100000 + k] || f[100000 - k]) { cout << k; break; }

易错：以为整个图只有一种划分 —— 实际每个连通块都可以独立翻转，这才是需要背包的原因。

B4拓扑排序应用

n 个任务，每个任务耗时 t[i] 且有前置任务。在无限并行资源下，求完成所有任务的最短时间。

查看参考答案

思路：这是「关键路径」问题。f[v] = t[v] + max{ f[u] | u 是 v 的前置 }，按拓扑序推，答案 = max(f[v])。

for (int i = 1; i <= cnt; i++) {
    int u = topo[i];
    f[u] = max(f[u], t[u]);          // 至少要做自己本身
    for (int v : e[u])
        f[v] = max(f[v], f[u] + t[v]);   // 前驱完成后才能开始 v
}
long long ans = 0;
for (int i = 1; i <= n; i++) ans = max(ans, f[i]);

易错：把「并行」误当成「串行」把 t 全部相加；或忘记把 t[v] 算进去，只累加了路径长度。

🔴 C组 · 挑战（4题）

C1综合分析

证明：一个无向图 G 是二分图，当且仅当 G 的每个连通分量都是二分图。

查看参考答案

⇒ 方向：若 G 存在划分 V = L ∪ R 使所有边跨类，则对任意连通分量 C，取 L' = L ∩ C、R' = R ∩ C，C 中每条边的两端仍分属 L' 与 R'，故 C 是二分图。

⇐ 方向：若每个连通分量 Cᵢ 都有自己的划分 Lᵢ / Rᵢ，令 L = ∪Lᵢ、R = ∪Rᵢ。由于不同连通分量之间没有边，所有边都在某个 Cᵢ 内，两端自然一在 L 一在 R，故 G 是二分图。

结论推广：「含奇环」也是按连通分量独立判断的。这就是染色算法可以「对每个连通块分别 BFS」的理论依据。

易错：认为不同连通分量的颜色必须一致（比如都从「0」开始）—— 实际上可以独立翻转。

C2难题

给定一张无向图，每条边有一个走一次的代价。求一条经过每条边恰好一次的路径的最小总代价 —— 若不存在欧拉通路，可以「重复走」某些边（走两次）使总路程最小，输出最小代价。

查看参考答案

这是中国邮递员问题（Chinese Postman Problem）。

步骤一：若所有点度数为偶，答案 = 所有边权之和。

步骤二：若存在 2k 个奇度点，需要把它们两两配对，在每对之间走一条最短路（这些边会被走两次），额外代价 = 配对的最短路长度之和。

步骤三：k ≤ n/2，用状压 DP 求「最小权完美匹配」：dp[S] 表示奇度点集合 S 已配对的最小额外代价，O(2^(2k) · k²)。

int oddList[MAXN], K;
long long dis[20][20], dp[1 << 18];
// 先 Floyd 求所有点对最短路，只保留奇度点之间的距离
for (int S = 1; S < (1 << K); S += 2) {   // S 必含最低位未配对的点
    int i = __builtin_ctz(S);
    dp[S] = INF;
    for (int T = S ^ (1 << i); T; T -= T & -T) {
        int j = __builtin_ctz(T);
        dp[S] = min(dp[S], dp[S ^ (1 << i) ^ (1 << j)] + dis[i][j]);
    }
}
// 答案 = 边权和 + dp[(1<<K)-1]

易错：忘记先把「边权和」加进去；或直接对奇度点做贪心配对（贪心不保证最优，必须状压 DP）。

C3图论建模

n 个点 m 条边的无向图，每条边至多走一次。求最多能走过多少条边（即最长「边不重复路径」）。

查看参考答案

思路：对每个连通块单独分析。设连通块有 e 条边、o 个奇度点。

· 若 o = 0：可以走完所有 e 条边（欧拉回路）。

· 若 o = 2：可以走完所有 e 条边（欧拉通路）。

· 若 o = 2k ≥ 4：需要把奇度点两两配对，走 k − 1 条「不重复路径」才能覆盖全部边。若只允许一条路径，则最多走 e − k + 1 条边。

结论公式：连通块最多能覆盖的边数 = e（当 o ≤ 2 时）；否则需要拆成多条路径，每条路径覆盖 e 条边中的一部分。

易错：忽略「边只能走一次」的限制，误当成可以重复走的最长路问题（后者是 NP-hard）。

C4初赛真题风格

一个有 8 个顶点的无向图，每个顶点的度数都是 3。问：① 这个图有多少条边？② 它是否存在欧拉回路？③ 它是否可能是二分图？

查看参考答案

① 边数：由握手定理 Σdeg = 2m，得 8 × 3 = 24 = 2m，所以 m = 12。

② 欧拉回路：8 个点度数全为 3（奇数），奇度点有 8 个，不是 0 个也非 2 个，所以不存在欧拉回路，也不存在欧拉通路。

③ 是否是二分图：不可能。二分图的两侧集合内无内部边，所有边都跨类。若 L 侧有 a 个点、R 侧有 b 个点（a + b = 8），则最大边数为 a·b ≤ 16。而本题 m = 12 ≤ 16，这个界不矛盾 —— 需要用「度数条件」重新分析。

更严谨的证法：二分图中，每条边的两个端点分属不同集合。设 L 内点度数和为 S_L、R 内为 S_R，则 m = S_L = S_R（每条边恰贡献一次给每侧）。又 S_L ≤ 3a、S_R ≤ 3b，即 12 ≤ 3a 且 12 ≤ 3b，得 a ≥ 4、b ≥ 4，又 a + b = 8，故 a = b = 4，此时 12 = 3×4 = S_L 成立，说明 L 内每个点都必须连满 3 条跨类边。

但由于 a = b = 4，任意一側的 4 个点之间的最大跨类边数为 4×4 = 16 ≥ 12，这个条件不构成矛盾。所以本题的③需要借助「3-正则二分图两侧点数必相等」来分析，答案取决于图的具体结构 —— 存在这样的图（如 K₄,₄ 去掉一个完美匹配的补图），因此理论上可能。

易错：直接凭「度数都是奇数」就断定不是二分图 —— 度数奇偶性与二分性没有直接关系（例：K₂ 是二分图，两个点度数都是 1）。

🏆 洛谷原题精选（12道）

以下 12 道题覆盖本讲的四类图：二分图染色与匹配、欧拉路径、DAG 拓扑排序与计数，按难度从低到高排列。

1
P5318
【深基18.例3】查找文献普及-
2
P1330
封锁阳光大学（二分图染色）普及+
3
P1113
杂务（拓扑排序 + DP）普及+
4
P1807
最长路（DAG 最长路）普及+
5
P4017
最大食物链计数（DAG 路径计数）普及+
6
P1038
[NOIP2003 提高组] 神经网络普及+
7
P1347
排序（拓扑排序判环）提高
8
P1341
无序字母对（欧拉路径）提高
9
P2731
[USACO3.3] 骑马修栅栏提高
10
P7771
【模板】欧拉路径提高
11
P3386
【模板】二分图最大匹配提高
12
P1525
关押罪犯（二分答案 + 二分图判定）提高