欧拉路径、欧拉回路与二分图的判定 | 王心俊老师信息学奥赛课件

板块	核心内容	对应大纲
欧拉路径定义	经过每条边恰好一次；回路要求回到起点	【8】欧拉路径
无向图判定	奇度点数为 0 或 2，且所有有边的点连通	【8】欧拉路径判定
有向图判定	回路上所有点 out = in；通路上恰有一对 +1/−1	【8】欧拉路径判定
Hierholzer	DFS 回溯插环、O(n+m)、递归 / 迭代两种写法	【8】Hierholzer 算法
字典序最小	邻接表排序 + 贪心选择最小出边	【8】欧拉路径变体
二分图判定	染色法（BFS / DFS 均可）、O(n + m)	【8】二分图判定
奇环等价	二分图 ⇔ 不含奇环	【8】二分图性质
最大匹配	匈牙利算法概念、增广路思想	【8】二分图匹配（了解）

模块 02

知识探究

先把"一笔画"的判定条件讲透，再学 Hierholzer 算法求出具体走法；然后用染色法解决二分图判定。

1一笔画：欧拉路径与欧拉回路核心概念

✏️ 从"可行性"到"构造"

欧拉通路：一条经过图中每条边恰好一次的路径。点可以重复经过，但边不能重复。不要求回到起点。

欧拉回路：起点与终点相同的欧拉通路。有欧拉回路的图叫"欧拉图"。

注意区分两个易混概念：

· 哈密顿路径：经过每个点恰好一次 —— 这是 NP 难问题，没有多项式算法！
· 欧拉路径：经过每条边恰好一次 —— 有 O(n+m) 的多项式算法。

很多同学第一次听到"一笔画"就想到哈密顿，那是完全不同的两类问题。本讲只讨论欧拉路径。

欧拉的核心观察：走在路径中间时，每"进入"一个点就必须"离开"它（除非它是起点或终点）。所以中间点的边必须"成对使用" —— 每个中间点的度数必须是偶数。只有起点和终点可以是奇数度（因为它们在端点上，进与出不必配对）。

立刻可得：无向图中奇度点的个数只能是 0（回路）或 2（通路）。奇度点个数为 1、3、4…… 都无解。

概念	经过什么恰好一次	是否要求回到起点	判定难度
欧拉通路	每条边	否	O(n+m)，本讲内容
欧拉回路	每条边	是	O(n+m)，本讲内容
哈密顿路径	每个点	否	NP 难 ⚠️
哈密顿回路	每个点	是	NP 难 ⚠️

哥尼斯堡七桥问题的答案：四块陆地的桥数分别是 3、3、3、5 —— 四个点全是奇点。要在一条路径里消耗掉这么多奇数度，最多只能有 2 个奇点（起点、终点），所以 不存在这样的走法，无论怎么走都会漏掉或重复。欧拉由此开创了图论。

✏️ 记住：欧拉问题看边（度数），哈密顿问题看点 —— 前者是简单算术，后者是 NP 难。

2无向图的判定条件：奇点 0 或 2 必背

〰️ 无向图判定完整版

存在欧拉回路 ⟺ 同时满足：
① 所有点的度数都是偶数；
② 图是连通的（严格说是"所有度 > 0 的点在同一个连通块里"，孤立点不影响）。

存在欧拉通路（但不一定存在回路） ⟺ 同时满足：
① 恰好有两个点的度数为奇数；
② 图是连通的（同样只看度 > 0 的点）。
此时这两个奇点就是路径的起点与终点（两者可以互换）。

为什么要加"连通"这一条？看一个反例：6 个点，边为 1-2、2-3、3-1（一个三角形），再加 4-5、5-6（一条链）。四边形的度数虽然满足条件，但三角形和链之间没有边相连 —— 一次连续行走不可能跨过两个独立的连通块，所以无解。

"边连通"的严谨说法：移除所有孤立点（度数为 0 的点）之后，剩余的图必须是连通的。孤立点因为没有边，不参与欧拉路径，可以忽略。

奇度点个数	是否有欧拉通路	是否有欧拉回路	起点选择
0 个	✅ 有	✅ 有	任意点（回路可任选起点）
2 个	✅ 有	❌ 无	必须是其中一个奇点
1 个	❌ 不可能出现	❌	手拉手定理保证偶数个奇点
4 个	❌ 无	❌	例如哥尼斯堡七桥
6 个	❌ 无	❌	一笔画需要多笔

5 个点、6 条边：度数 1:4、2:2、3:2、4:2、5:2 —— 全偶且连通 ⇒ 存在欧拉回路

这就是"插环"的直观图景

先沿蓝色环走一圈：1 → 2 → 3 → 1，回到起点。
但粉色环上的边还没走（1-4、4-5、5-1）。
从 1 号点"岔出去"，把粉色环也走完：1 → 4 → 5 → 1。
两个环在公共点 1 处被"拼"成一条路：1 → 2 → 3 → 1 → 4 → 5 → 1。

💡 Hierholzer 算法做的就是"不断找到新环并把它拼进已有路径"。

📌 判定三步走：① 算度数 ② 数奇点（0 或 2）③ 检查边连通性。

3有向图的判定条件：出度与入度

➡️ 有向图判定完整版

有向图里，每条边有方向，所以"进"和"出"要分开数。

存在欧拉回路 ⟺ 同时满足：
① 所有点都满足 outdeg[i] == indeg[i]；
② 所有度 > 0 的点在同一个弱连通块里（把有向边看无向边时连通）。

存在欧拉通路（无回路） ⟺ 同时满足：
① 恰好存在一个点满足 outdeg − indeg = 1（它必须是起点）；
② 恰好存在一个点满足 indeg − outdeg = 1（必须是终点）；
③ 其余所有点都满足 outdeg == indeg；
④ 弱连通。

为什么是"差 1"？路径中间的点同样"进一次出一次"，出入相等；起点"多出一次"（一开始就在那、不需要进来），终点"多进一次"（最后停在那、不需要出去）。

常见错误：把有向图的判定强行套到无向图的"度数"上。有向图不能用"度数奇偶"来判断，必须用"入度 / 出度是否相等"。

图的类型	欧拉回路条件	欧拉通路条件（非回路）
无向图	所有点度数为偶 + 连通	恰 2 个奇点 + 连通
有向图	所有点 outdeg == indeg + 弱连通	恰一对 (+1, −1) + 其余相等 + 弱连通

⚠️ 关键前提：无论是无向还是有向，都必须先检查"所有有边的点是否连通"！度数条件满足了但图不连通，一样无解。

4Hierholzer 算法：回溯插环，O(n + m) 本讲重点

🔄 算法思想

Hierholzer（1873 年提出）的思路非常优雅：

第 1 步：从起点出发，沿着未走过的边一路走下去，每走一条边就把它标记为"已用"。因为除了起点/终点之外每个点的度数都是偶数，"进来必有出路"，所以这条路一定会卡死在起点或终点（走不动时，一定是所有边都用完了或者无路可走）。

第 2 步：走不动时，把当前点压入答案序列，然后回退到上一个点，看看它还有没有未走过的边。

第 3 步：如果有，就从那里再走一条新路（一定会绕回该点，形成一个"环"），走完后再回退。如此反复。

第 4 步：把答案序列倒序输出，就是欧拉路径。

为什么倒序？因为"最后压入的点"是路径的终点，而答案序列的压栈顺序是"从终点往起点"，所以要反转。

为什么正确？每次"走不动"时压入的点，其所有出边都已用过，所以它在最终路径中一定处于"最后"的位置 —— 这与"回溯拼接"的直觉一致：后完成的回环被插到前面。

复杂度：每条边恰好被访问和消耗一次 O(m)，每个点入栈出栈一次 O(n)，总 O(n + m)。

▶ Hierholzer 回溯插环演示（5 点 6 边）

0度数全偶（1:4、2:2、3:2、4:2、5:2）且连通 ⇒ 存在欧拉回路。从 1 号点出发（回路起点任意）。答案栈 ans = []。

1顺着未用边走：1 → 2（标记边 1-2 已用）。在 2 号点，未用的出边只有 2-3，继续走。

22 → 3，再从 3 走 3 → 1（边 3-1 未用）。此时回到了 1 号点，而 1 的未用边还有 1-4。

3继续走 1 → 4 → 5 → 1。回到 1 号点后，1 的所有边都已用过 → 无路可走，把 1 压入答案栈：ans = [1]。

4回溯：5 号点已无未用边 → 压入，ans = [1, 5]；4 号点同理 → ans = [1, 5, 4]；回到 1 → ans = [1, 5, 4, 1]。

5继续回溯：3 号点已无未用边 → ans = [1,5,4,1,3]；2 号点 → ans = [1,5,4,1,3,2]；1 号点 → ans = [1,5,4,1,3,2,1]。栈空，结束。

6倒序输出：1 → 2 → 3 → 1 → 4 → 5 → 1 —— 正好是一次走遍全部 6 条边的欧拉回路！

要点："走不动了就记录并回退"是 Hierholzer 的灵魂。倒序输出才是正确的路径方向。

🔍 再看一个"真正需要插环"的例子

5 个点，边为 1-2、2-3、3-1（三角形）、3-4、4-5、5-3（另一个三角形）。度数：1:2、2:2、3:4、4:2、5:2 → 全偶且连通，存在欧拉回路。

从 1 出发：先走 1→2→3→1，此时回到 1 号点，1 的所有边都用完了，压入 ans = [1]；回退到 3 号点，发现 3-4 还没走 → 继续走 3→4→5→3，回到 3 号点，3 的边也用完了 → 压入 ans = [1, 3]；接着回溯压入 5、4、3、2、1 → ans = [1, 3, 5, 4, 3, 2, 1]。

倒序输出：1 → 2 → 3 → 4 → 5 → 3 → 1

可以看到：三角形 1-2-3-1 与三角形 3-4-5-3 在公共点 3 处被"拼接"在了一起 —— 这正是"插环"的直观含义。

C++Hierholzer · 迭代版（推荐，无爆栈风险）

const int MAXN = 100005;
struct Edge { int to, nxt; } e[MAXM];
int head[MAXN], cntE = 0;
int cur[MAXN];                 // 当前弧优化：记录 u 已经处理到哪条边

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

int stk[MAXN], top = 0;       // 手写栈模拟 DFS 路径
int ans[MAXM], cntAns = 0;

void hierholzer(int s) {
    stk[++top] = s;
    while (top) {
        int u = stk[top];
        if (cur[u]) {                  // 还有未走过的边
            int id = cur[u];
            cur[u] = e[id].nxt;         // 消耗这条边（移动到下一条）
            stk[++top] = e[id].to;      // 走过去
        } else {                        // 无边可走 → 记录并回退
            ans[++cntAns] = u;
            top--;
        }
    }
    // ans[1..cntAns] 是倒序的路径，从 cntAns 往 1 输出
    for (int i = cntAns; i >= 1; i--)
        cout << ans[i] << " \n"[i == 1];
}

🔄 递归版（更简洁但有风险）

void dfs(int u) {
    for (int i = head[u]; i; i = e[i].nxt) {
        if (vis[i]) continue;
        vis[i] = true;                  // 无向图要 vis[i^1] = true
        dfs(e[i].to);
    }
    ans.push_back(u);                   // 后序记录
}

⚠️ 当 m 达到 10⁵ 时，递归深度可能达到 10⁵ 层，必定爆栈。正式比赛请用左侧的迭代版。

⚡ 当前弧优化（cur 数组）

朴素写法每次回到 u 都从头遍历 u 的邻接表，如果 u 的度数很大（例如 10⁵），会被重复扫描很多次，复杂度退化成 O(nm)。

cur[u] 记录"u 已经处理到哪条边了"，每次从 cur[u] 继续，保证每条边只被"看过一次"，总复杂度回到 O(n + m)。

🌟 这个技巧在 Dinic 最大流里也出现过，是图论里的通用常数优化。

🔄 口诀：一路走到黑，走不动就记账（压栈）后退；全部退完，倒着念就是答案。

5字典序最小的欧拉路径常考变体

🔤 怎样让答案字典序最小？

很多题目（例如 P7771、P1341）要求"输出字典序最小的欧拉路径"。做法只有两步：

第 1 步：把每个点的邻接表按"终点编号从小到大"排序。这样遍历时总是先尝试最小的那条出边。

第 2 步：直接用 Hierholzer 走一遍。它会自然地优先选择编号小的边，从而得到字典序最小的答案。

为什么贪心是对的？可以参考"字典序最小拓扑序"的论证：每一步我们都希望下一位尽可能小；而当有多个可选的出边时，选最小的那个不会破坏"剩余图仍能走完"这件事（因为 Hierholzer 保证了"只要度数条件还成立，就一定还能走完"）。这是一个标准的贪心归纳。

关键细节：如果是无向图，排序时要考虑"哪些边一开始就存在"，不能把"反向边走回来的那条"也算进去；一般的处理是先读入所有边，按 (min(u,v), max(u,v)) 或按"从 u 出发能到的 v"排序。

复杂度：排序 O(m log m) + Hierholzer O(n + m)。

C++字典序最小欧拉路径（有向图 · vector 存图版）

int n, m;
vector<int> g[MAXN];              // g[u] 存 u 的所有出边终点
int outdeg[MAXN], indeg[MAXN];
vector<int> ans;

void dfs(int u) {
    while (!g[u].empty()) {
        int v = g[u].back();       // 从后面取（配合倒序排序更省事）
        g[u].pop_back();            // 消耗掉这条边
        dfs(v);
    }
    ans.push_back(u);               // 无路可走时压入
}

int main() {
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        outdeg[u]++; indeg[v]++;
    }

    // ① 关键：邻接表排序（从大到小，配合 back() 弹出 → 从小到大）
    for (int i = 1; i <= n; i++)
        sort(g[i].begin(), g[i].end(), greater<int>());

    // ② 找起点：优先找 out−in == 1 的点；否则从最小的有边的点出发
    int s = 0;
    for (int i = n; i >= 1; i--)
        if (outdeg[i] - indeg[i] == 1) { s = i; break; }
    if (!s) for (int i = 1; i <= n; i++)
        if (outdeg[i]) { s = i; break; }

    dfs(s);
    for (int i = (int)ans.size() - 1; i >= 0; i--)
        cout << ans[i] << " \n"[i == 0];
}

💡 注意起点至少要满足"有边"这个条件。如果图里存在多个连通块或孤立点，从 0 号点出发会得不到完整答案 —— 所以起点的选取必须是"outdeg - indeg == 1 的点"，否则"第一个有边的点"。

6二分图与染色法：一次遍历就能判定核心算法

🎨 定义与直观

二分图：把顶点集分成两个部分 X 和 Y，使得每条边的两个端点分别落在 X 和 Y（同一部分内的点之间没有边）。

等价说法（染色）：给每个点染黑或白，要求"相邻点颜色不同"。能成功染色 ⇔ 是二分图。

染色法（BFS 或 DFS 都可以）：

① 任选一个未访问的点 s，染成颜色 0（假设是黑色），把它入队。

② 从队列取出点 u，遍历它所有的邻点 v：
　· 若 v 还没染色 → 把 v 染成 color[u] ^ 1（异色），入队；
　· 若 v 已经染色且 color[v] == color[u] → 出现矛盾，判定不是二分图，直接返回。

③ 队列空后，还要继续对下一个未访问的点做同样处理（因为图可能不连通，每个连通块都要检查）。

复杂度：每个点访问一次、每条边检查两次（无向图），总 O(n + m)。

染色的结果：{1, 2, 3} 为一部，{4, 5, 6} 为另一部，每条边都跨越两部

染色过程（对应左侧图）

从 1 号点开始，染成 颜色 0。
1 的邻居是 4、5 → 都染成 颜色 1。
4 的邻居是 1、3 → 1 已染 0（异色 ✅），3 染成 颜色 0。
5 的邻居是 1、2 → 2 染成 颜色 0。
2 的邻居是 5、6 → 6 染成 颜色 1；3 的邻居是 4、6 → 都是颜色 1（异色 ✅）。
全程无冲突 ⇒ 是二分图。结果为 {1,2,3} ∪ {4,5,6}。

C++二分图染色判定（BFS 版）

int color[MAXN];              // -1 未染色 / 0 一种颜色 / 1 另一种颜色
vector<int> g[MAXN];

bool isBipartite(int n) {
    for (int i = 1; i <= n; i++) color[i] = -1;   // 全部初始化为未染色

    for (int s = 1; s <= n; s++) {              // 图可能不连通，逐块处理
        if (color[s] != -1) continue;

        queue<int> q;
        color[s] = 0;
        q.push(s);

        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                if (color[v] == -1) {                // 未染色 → 染成异色
                    color[v] = color[u] ^ 1;
                    q.push(v);
                } else if (color[v] == color[u]) {   // 同色相邻 → 冲突
                    return false;
                }
            }
        }
    }
    return true;
}

💡 color[u] ^ 1 是一个常用小技巧：0 ^ 1 = 1、1 ^ 1 = 0，正好实现"取反色"。比写 1 - color[u] 或 !color[u] 更直观（后者会得到 bool）。

💡 想一想

为什么说"染色矛盾 ⇔ 存在奇环"？请看下一小节的严格论证。这里先给出直觉：沿着一个长度为 L 的环走一圈，每走一步颜色就翻转一次；回到起点时颜色必须与出发时相同，这就要求 L 是偶数。若 L 是奇数，就会得到"起点颜色 = 起点的反色"这种矛盾。

7奇环等价性：二分图 ⇔ 不含奇环

⭕ 两个方向的论证

（1）若图是二分图，则不含奇环。

设点的两部分为 X、Y。沿任意一个环 v₁ → v₂ → … → v_L → v₁ 走一圈。由于相邻点必在不同部分，v₁, v₂, v₃, … 会交替出现在 X、Y 中。要回到 v₁，必须"从另一边跳回来"，所以环长 L 必须是偶数。故二分图不含奇环。

（2）若图不含奇环，则可以用染色法染成二分图。

任选一个点染 0，然后按 BFS 顺序把每个点的邻点染成异色（这就是染色法）。要证明它不会出现矛盾 —— 反证：假设某条边 (u,v) 的两端被染成了同色。那么在 BFS 树里，u 和 v 分别到根的路径长度同奇偶，于是 "LCA→u→v→LCA" 构成的环长度为奇数 + 1 = 奇数，与"不含奇环"矛盾。

结论：二分图 ⇔ 不含奇环 ⇔ 染色不冲突。三者是同一件事的三种说法。

图的特征	是否二分图	说明
树（无环）	✅ 是	没有任何环，自然没有奇环
偶环（长度 4、6…）	✅ 是	交替染色可以闭合
奇环（长度 3、5、7…）	❌ 不是	染色必然冲突
两个独立连通块（都是二分图）	✅ 是	分别染色，互不干扰
孤立点	✅ 是	可以随便归到任一部分
自环（u-u）	❌ 不是	自环可看成"长度 1 的奇环"

⭕ 一句话：有奇环就不是二分图；二分图里所有环都是偶环。自环是最短的奇环（长度 1）。

8二分图最大匹配（概念了解）

🔗 什么是匹配

匹配：在二分图中选出若干条边，使得任意两条边都不共用端点。选出的边数叫匹配的大小。边数最大的匹配叫最大匹配。

生活化的说法：左边是学生、右边是志愿项目，每个学生最多参加一个项目、每个项目最多接收一个学生。最多能配成多少对？这就是最大匹配。

匈牙利算法（Kuhn / 增广路算法）的核心思想：

① 依次尝试为左边每个点找一个对象。
② 对当前点 u，随便找一个未匹配的右邻点 v → 直接配对成功。
③ 如果 v 已被别的点 x 配走了，就尝试给 x 换一个对象（递归地再找）。如果 x 成功换到了别的对象，那 u 就可以配 v 了。
④ 这种"重新安排旧配对"的过程叫增广，沿着"未匹配边 → 匹配边 → 未匹配边 → …"的交替路径一直找。

复杂度：O(n × m)（每个点跑一次 DFS/BFS），n 为单侧点数。

等价定理（König 定理）：二分图中，最大匹配的大小 = 最小点覆盖的大小。这是一条非常漂亮的结论，在很多题目里能把"覆盖"问题转化成"匹配"问题。

本讲的定位：这是提高组需要"知道名字、知道思路、能套模板"的内容，深入证明超纲。遇到"配对 / 分配 / 覆盖"类问题，第一反应应该是"能不能建模成二分图匹配"。

🔗 见到"一一配对的分配问题"，先问一句：这是不是二分图最大匹配？（模板题：P3386）

9判定与算法对比选型

任务	核心条件 / 方法	复杂度	关键点
无向图欧拉回路	所有点度数为偶 + 连通	O(n + m)	孤立点可忽略
无向图欧拉通路	恰 2 个奇点 + 连通	O(n + m)	起点必须是奇点
有向图欧拉回路	所有点 out == in + 弱连通	O(n + m)	不能用"度数奇偶"判
有向图欧拉通路	恰一对 (+1, −1) + 其余相等	O(n + m)	起点是 +1 的那个
求欧拉路径（Hierholzer）	DFS 走边 + 回溯压栈 + 倒序	O(n + m)	加 `cur[]` 当前弧优化
字典序最小欧拉路径	邻接表排序 + Hierholzer	O((n+m) log m)	从大到小排序 + back() 弹出
二分图判定	染色法（BFS/DFS）	O(n + m)	每个连通块都要检查
二分图最大匹配	匈牙利算法（增广路）	O(n m)	模板题 P3386

题目关键词	想到什么	理由
"每条边走一次"、"一笔画"、"扫雪"	欧拉路径	经过边恰好一次
"回到起点"	欧拉回路（度数条件更严）	要求所有点度数为偶
"把点分成两组 / 有矛盾不能同组"	二分图染色	相邻必须异色
"一一配对 / 分配 / 最大对数"	二分图最大匹配	每条边最多选一次
"每条边至少覆盖一个端点"	最小点覆盖 = 最大匹配	König 定理
"字典序最小的方案"	邻接表排序 + 贪心	每次选最小的边

案例案例1：P7771【模板】欧拉路径模板题

题目：给定 n 个点、m 条边的有向图，求它的字典序最小的欧拉路径。若不存在，输出 No。

🔍 详细分析过程

第1步：判定 —— 统计每个点的出度与入度。若存在 outdeg[i] − indeg[i] == 1 的点，那它就是起点；若不存在这样的点，则要求所有点 outdeg == indeg（回路），此时起点取编号最小的有边的点。

第2步：合法性校验 —— ① 差值只能是"一个 +1、一个 −1"，或者"全部为 0"；② 同时要检查弱连通（所有有边的点在同一个连通块里）。

第3步：字典序最小 —— 把每个点的出边列表按终点编号从小到大排序。

第4步：Hierholzer —— 从起点出发走一遍，无路可走时压栈，最后倒序输出。

第5步：输出长度校验 —— 若答案长度 ≠ m + 1，说明图不连通，输出 No。

易错：① 忘记检查弱连通；② 起点选取错误（一定要优先选 out − in == 1 的点）；③ 排序方向搞反导致字典序不是最小；④ m 很大时递归会爆栈，务必用迭代版。

C++P7771 欧拉路径 · 完整代码

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

const int MAXN = 100005;
int n, m;
vector<int> g[MAXN];            // 出边终点列表
int outdeg[MAXN], indeg[MAXN];
int stk[MAXN * 2], top = 0;
int ans[MAXN * 2], cntAns = 0;
int ptr[MAXN];                    // 当前弧优化

// 迭代版 Hierholzer（避免递归爆栈）
void hierholzer(int s) {
    stk[++top] = s;
    while (top) {
        int u = stk[top];
        if (ptr[u] < (int)g[u].size()) {
            int v = g[u][ptr[u]++];    // 消耗一条出边
            stk[++top] = v;
        } else {
            ans[++cntAns] = u;
            top--;
        }
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        outdeg[u]++; indeg[v]++;
    }

    // ① 判定奇异性并确定起点
    int s = 0, cntPlus = 0, cntMinus = 0;
    for (int i = 1; i <= n; i++) {
        int d = outdeg[i] - indeg[i];
        if (d == 1) { cntPlus++; s = i; }        // 起点候选
        else if (d == -1) cntMinus++;
        else if (d != 0) { cout << "No" << endl; return 0; }
    }
    if (!((cntPlus == 1 && cntMinus == 1) || (cntPlus == 0 && cntMinus == 0))) {
        cout << "No" << endl; return 0;
    }
    if (!s)                                  // 回路：取编号最小的有边点
        for (int i = 1; i <= n; i++)
            if (outdeg[i]) { s = i; break; }
    if (!s) { cout << "No" << endl; return 0; }   // 全为孤立点

    // ② 字典序最小：出边从小到大排序
    for (int i = 1; i <= n; i++)
        sort(g[i].begin(), g[i].end());

    // ③ Hierholzer
    hierholzer(s);

    // ④ 校验：边全部走完则答案长度为 m+1
    if (cntAns != m + 1) { cout << "No" << endl; return 0; }

    for (int i = cntAns; i >= 1; i--)
        cout << ans[i] << " \n"[i == 1];
    return 0;
}

运行结果（欧拉回路）

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

（所有点 outdeg == indeg：
  1: out 2, in 2  ✅
  2: out 1, in 1  ✅
  3: out 1, in 1  ✅
  4: out 1, in 1  ✅
  5: out 1, in 1  ✅
 起点取编号最小的有边点 = 1）

运行结果（欧拉通路）

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

（差值 out−in：1:+1（起点）、5:−1（终点）、其余 0
 路径 1→2→3→1→4→5 走遍全部 5 条边）

运行结果（无解）

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

（两个互不相连的环 1-2-1 与 3-4-3：
 每个点 outdeg == indeg，度数条件全部满足，
 但图不连通 —— 走完其中一条边后就再也走不到另一个环了
 代码里表现为 cntAns = 3 ≠ m + 1 = 5 → 输出 No）

💡 想一想

为什么"答案长度 ≠ m + 1"就代表无解？因为一次欧拉路径要走遍 m 条边，会经过 m + 1 个点（点可以重复）。如果答案序列少于 m+1 个点，说明有边没走到 —— 那一定是因为图不连通（另一块里的边走不到）。这是判断连通性的一种非常简洁的方式。

还有一个容易忽略的坑：自环。例如边 1→1，它让 outdeg[1] 和 indeg[1] 各 +1，所以不影响差值判断；但 Hierholzer 走它的时候要保证"走的是一条还没走过的边"。如果用"用邻接矩阵 + 直接删除边"的方式实现，自环要特别小心（因为 g[u][u] 会被访问两次）。

案例案例2：P1341 无序字母对 · 字典序最小欧拉路径经典应用

题目：给定 n 个无序字母对（例如 ab 表示字母 a 和 b 相邻），要求构造一个长度为 n+1 的字符串，使得每个字母对都在字符串中相邻出现恰好一次。输出字典序最小的方案；若无解输出 No Solution。

🔍 建模：把字母当点，字母对当边

第1步：建图 —— 52 个可能的字母（'a'~'z' 和 'A'~'Z'）作为点，每个"无序字母对"作为一条无向边。

第2步：转化问题 —— "字符串中每一对字母恰好相邻一次"意味着每条边恰好被走一次，这正是一个欧拉路径问题！字符串的长度 n+1 就是路径经过的点数。

第3步：判定条件（无向图） —— ① 奇度点个数必须是 0 或 2；② 有边的点必须连通。

第4步：确定起点 —— 若有两个奇点，起点必须是字典序较小的那个奇点；若无奇点（存在欧拉回路），起点取字典序最小的有边点。

第5步：答案最小 —— 把每个点的邻接表按字母字典序升序排序，然后跑 Hierholzer，最后倒序输出即可。

易错：① 字母区分大小写（'A' 与 'a' 是不同的点）；② 输出的是字符序列而不是数字；③ 起点的选择要兼顾"奇点"与"字典序最小"两个条件；④ 自环边（例如 aa）要处理成度数 +2。

运行结果示例

输入: 5
      ab
      bc
      cd
      de
      ea
输出: abcde

（a-b-c-d-e-a 构成一个 5 环，所有点度数都是 2（全偶），
 从字典序最小的有边点 a 出发，得到字典序最小的答案 "abcde"）

输入: 4
      ab
      bc
      cd
      da
输出: abcd

（路径 a-b-c-d-a，奇点个数 0，起点取 a）

输入: 3
      ab
      bc
      ca
输出: abc

（三角形 a-b-c-a：奇点 0 个，起点 a，答案 "abc"）

输入: 3
      ab
      bc
      cd
输出: abcd

（奇点为 a 和 d（度数都是 1）→ 起点必须是 a（字典序较小的奇点））

💡 这道题的关键转换是"字符 → 点、无序字母对 → 无向边"。把 52 个字母映射到 0..51 或直接按 ASCII 存到 128 大小的数组里都可以。遇到"构造一个序列使得相邻关系恰好满足给定的集合"这类题，几乎都是欧拉路径。

案例案例3：P1330 封锁阳光大学 · 二分图染色应用建模经典

题目：给定一张无向图。要求选出一些点"放置监视器"，使得每条边的两个端点中恰好有一个被选中（即相邻两点不能被同时选中，也不能同时不选）。求最少需要选多少个点；若做不到，输出 Impossible。

🔍 建模思路

第1步：识别"恰好一个被选中" —— 这等价于"相邻两点必须一选一不选"，也就是"相邻两点颜色不同" —— 正是二分图染色的条件！

第2步：判定可行性 —— 如果染色过程中出现冲突（相邻同色），说明图中存在奇环，无解 → 输出 Impossible。

第3步：统计答案 —— 染色后，每个连通块内有两种颜色可以选："选颜色 0 的所有点"或"选颜色 1 的所有点"。为了让总点数最少，每个连通块都应该取较少的那一种。

第4步：求和 —— 把每个连通块的 min(cnt₀, cnt₁) 累加起来就是答案。

重要细节：颜色 0 / 颜色 1 是可以整体对调的（交换后染色仍然合法）。所以每个连通块都有两种方案，取小的那种即可。不能全局统一取一种颜色，因为不同连通块的对调是独立的。

易错：① 忘记多连通块都要处理；② 只在第一个连通块上做了 min 就输出（漏掉其他块）；③ 有解时输出的不是"最多能选多少"而是"最少要选多少"。

C++P1330 封锁阳光大学 · 完整代码

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

const int MAXN = 100005;
int color[MAXN];
vector<int> g[MAXN];

int cnt[2];        // 当前连通块两种颜色的点数

bool bfs(int s) {
    queue<int> q;
    color[s] = 0;
    cnt[0] = 1; cnt[1] = 0;
    q.push(s);

    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (color[v] == -1) {
                color[v] = color[u] ^ 1;
                cnt[color[v]]++;
                q.push(v);
            } else if (color[v] == color[u]) {
                return false;             // 染色冲突 → 有奇环
            }
        }
    }
    return true;
}

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);
        g[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) color[i] = -1;

    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        if (color[i] != -1) continue;
        if (!bfs(i)) { cout << "Impossible" << endl; return 0; }
        ans += min(cnt[0], cnt[1]);     // 每个块取较小的那一侧
    }

    cout << ans << endl;
    return 0;
}

运行结果

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

（一条 5 个点的链：染色得 {1,3,5} 颜色 0、{2,4} 颜色 1
 取较小的一侧 = 2 个点（选 2 号和 4 号）
 检查：边 1-2 恰好选了 2 ✅、2-3 恰好选了 2 ✅、3-4 恰好选了 4 ✅、4-5 恰好选了 4 ✅）

运行结果（无解）

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

（三角形是奇环，染色必然冲突 —— 例如 1 染 0，2 染 1，3 被 2 要求染 0，
 但 3 又和 1 相邻、1 是 0，冲突 → Impossible）

💡 想一想

如果把题目改成"每条边至少有一个端点被选中"，那就变成了"最小点覆盖"问题。对二分图而言，由 König 定理，最小点覆盖 = 最大匹配。所以同一张图，问法不同，解法就完全不同 —— 读题时务必分清"恰好一个"和"至少一个"。

模块 03

实践应用

三道递进练习：先做一笔画判定，再练二分图染色，最后完整构造一条欧拉路径。

A1基础应用题

一笔画判定：判断下面三张图能否一笔画（走遍每条边恰好一次）。（甲）5 个点，边为 1-2、2-3、3-1、1-4、4-5、5-1；（乙）4 个点，边为 1-2、2-3、3-1、3-4；（丙）5 个点，边为 1-2、2-3、3-4、4-5、1-3。

提示：只算度数、数奇点，再看连通性。

查看参考答案

（甲）度数：1 连 2、3、4、5 → 4 度；2 连 1、3 → 2 度；3 连 2、1 → 2 度；4 连 1、5 → 2 度；5 连 4、1 → 2 度。

奇点个数 = 0，且连通 ⇒ 存在欧拉回路，能从任意点出发并返回。例如：1 → 2 → 3 → 1 → 4 → 5 → 1

（乙）度数：1 连 2、3 → 2 度；2 连 1、3 → 2 度；3 连 2、1、4 → 3 度（奇）；4 连 3 → 1 度（奇）。

奇点个数 = 2（3 号点和 4 号点），且连通 ⇒ 存在欧拉通路（无回路），必须从 3 或 4 出发。例如：3 → 1 → 2 → 3 → 4

（丙）度数：1 连 2、3 → 2 度；2 连 1、3 → 2 度；3 连 2、4、1 → 3 度（奇）；4 连 3、5 → 2 度；5 连 4 → 1 度（奇）。

奇点个数 = 2（3 号点和 5 号点），且连通 ⇒ 存在欧拉通路，必须从 3 或 5 出发。例如：5 → 4 → 3 → 2 → 1 → 3

✅ 注意（乙）和（丙）都有 2 个奇点，所以存在通路但不存在回路 —— 不可能回到出发点。

B1进阶应用题

二分图染色：判断下面两张图是否为二分图，若是请给出两部分的划分。（甲）6 个点，边为 1-2、2-3、3-4、4-5、5-6、6-1；（乙）4 个点，边为 1-2、2-3、3-4、4-1、1-3。

提示：从一个点出发交替染色，看是否出现相邻同色。

查看参考答案

（甲）6 个点的偶环：是二分图

从 1 号点染颜色 0：1(0) → 2(1) → 3(0) → 4(1) → 5(0) → 6(1) → 回到 1，1 已经是 0，与 6 的 1 不同 ✅，无冲突。

划分：{1, 3, 5} 与 {2, 4, 6}

（乙）4 个点 + 一条对角线：不是二分图

从 1 号点染 0：1(0) → 2(1) → 3(0)（由 2 要求）→ 4(1)（由 3 要求）。但 4 还与 1 相邻，1 是 0、4 是 1，不同色 ✅。接着检查边 1-3：1 是 0、3 是 0 —— 同色冲突！

结论：不是二分图。原因是图中存在奇环 1-3-4-1（长度 3）。

💡 快速判断法：图中只要存在长度是奇数的环，就不是二分图。（乙）里的三角形环 1-3-4-1 一眼可见。

C1综合应用题

欧拉路径构造：有向图 5 个点、6 条边，边为 1→2、2→3、3→1、1→4、4→5、5→1。请判定并给出字典序最小的欧拉路径（用 Hierholzer 手动走一遍）。

提示：先算出度入度，确定起点，然后让每个点尽量走编号最小的出边。

查看参考答案

出度 / 入度：

1: out 2（2, 4）, in 2（来自 3, 5） → 差 0
2: out 1（3）, in 1（来自 1） → 差 0
3: out 1（1）, in 1（来自 2） → 差 0
4: out 1（5）, in 1（来自 1） → 差 0
5: out 1（1）, in 1（来自 4） → 差 0

所有点差值均为 0 ⇒ 存在欧拉回路。起点取编号最小的有边点 = 1。

Hierholzer 手动过程（邻接表已升序排序）：

① 从 1 出发，选最小的出边 1→2；在 2 走 2→3；在 3 走 3→1，回到 1。此时 1 还有未用边 1→4。

② 继续 1→4→5→1，回到 1；1 的所有出边用完 → 压栈 ans = [1]。

③ 回溯：5 无未用边 → [1,5]；4 → [1,5,4]；回到 1 → [1,5,4,1]；3 无未用边 → [1,5,4,1,3]；2 → [1,5,4,1,3,2]；1 → [1,5,4,1,3,2,1]。

④ 倒序输出：1 → 2 → 3 → 1 → 4 → 5 → 1

验证：用到的边依次是 1-2、2-3、3-1、1-4、4-5、5-1 —— 恰好是全部 6 条边，每条一次 ✅

✅ 这条路径就是字典序最小的：从 1 出发可选的出边有 {2, 4}，选 2；在 2 只有一条出边 3；在 3 只有一条出边 1；在 1 剩 {4}，选 4 …… 全程都选了最小的可用边。

模块 04

总结提升

①核心要点与万能模板

考点	关键结论	必须记住的细节
欧拉通路	经过每条边恰好一次，不要求回到起点	点可以重复，边不能重复
无向图回路	所有点度数为偶 + 连通	孤立点可忽略
无向图通路	恰 2 个奇点 + 连通	起点必须是奇点
有向图回路	所有点 outdeg == indeg + 弱连通	不能用度数奇偶判
有向图通路	恰一对 (+1, −1) + 其余相等	起点是 +1 的点
连通性检验	答案长度 == m + 1	最短的连通性检验方式
Hierholzer	走 → 无路可走就压栈 → 回退 → 倒序输出	加 `cur[]` 当前弧优化
爆栈风险	m 大时必须用迭代版	递归深度可达 10⁵
字典序最小	邻接表排序 + Hierholzer	从小到大排序
二分图判定	染色法，相邻异色	每个连通块都要检查
奇环等价	二分图 ⇔ 无奇环	自环是长度 1 的奇环
最大匹配	匈牙利算法，O(nm)	König：最大匹配 = 最小点覆盖

C++万能模板一：欧拉路径判定 + Hierholzer

/* ===== 无向图判定（degree[] 为度数） ===== */
int odd = 0;
for (int i = 1; i <= n; i++) if (degree[i] & 1) odd++;
if (odd != 0 && odd != 2) { cout << "无解"; };
// odd == 0 从任意有边点出发；odd == 2 必须从某个奇点出发

/* ===== 有向图判定（outdeg / indeg） ===== */
int s = 0, cp = 0, cm = 0;
for (int i = 1; i <= n; i++) {
    int d = outdeg[i] - indeg[i];
    if (d == 1) { cp++; s = i; }
    else if (d == -1) cm++;
    else if (d != 0) { cout << "无解"; }
}
// 合法条件：(cp==1 && cm==1) 或 (cp==0 && cm==0)

/* ===== Hierholzer（迭代版，vector 存图） ===== */
vector<int> g[MAXN], ans;
int ptr[MAXN], stk[MAXN * 2], top = 0;

void hierholzer(int s) {
    stk[++top] = s;
    while (top) {
        int u = stk[top];
        if (ptr[u] < (int)g[u].size())
            stk[++top] = g[u][ptr[u]++];
        else { ans.push_back(u); top--; }
    }
    reverse(ans.begin(), ans.end());          // 必须倒序！
    if ((int)ans.size() != m + 1) cout << "无解（不连通）";
}

C++万能模板二：二分图染色判定

int color[MAXN];
vector<int> g[MAXN];

bool isBipartite(int n) {
    for (int i = 1; i <= n; i++) color[i] = -1;
    for (int s = 1; s <= n; s++) {
        if (color[s] != -1) continue;      // 图可能不连通
        queue<int> q; color[s] = 0; q.push(s);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : g[u]) {
                if (color[v] == -1) { color[v] = color[u] ^ 1; q.push(v); }
                else if (color[v] == color[u]) return false;
            }
        }
    }
    return true;
}

🎯 思维定式

看到 "每条边走一次 / 一笔画" → 欧拉路径（数奇点 / 算差值）；看到 "分成两组 / 不相邻 / 有无矛盾" → 二分图染色（找奇环）。

②拓展案例

拓展1混合图欧拉回路：无向边定向 + 网络流超纲了解

问题：图里既有有向边，又有无向边，判断是否存在欧拉回路。

🔍 核心思路

第1步：先把每条无向边随便定一个方向（比如都定成 u→v），得到一个纯有向图。

第2步：检查每个点的 outdeg − indeg。若某个差值不是偶数，直接无解（因为翻转一条无向边只会让两端的差值各改变 2）。

第3步：把所有 outdeg > indeg 的点（"出度多了"）和 indeg > outdeg 的点（"入度多了"）挑出来，通过翻转某些无向边来平衡差值。

第4步：翻转一条无向边 u→v 变成 v→u，会让 u 的出度 −1、入度 +1（差值 −2），v 反过来（差值 +2）。所以这是一个"把多余出度转移给缺点"的问题 —— 用网络流建模：超级源点连向"出度多的点"（容量 = 差值 / 2），"入度多的点"连向超级汇点，无向边（已定向）作为中间边。若最大流等于总的多余量，则存在欧拉回路。

本讲的定位：这是网络流的经典应用，属于提高+/省选内容，这里只要求"知道有这么个做法"。

🔀 混合图欧拉 = 先随意定向 → 用无向边调整差值 → 网络流建模。

拓展2二分答案 + 二分图判定：关押罪犯 (NOIP2010 P1525) 经典组合

问题：n 名罪犯，m 对之间有仇恨值。要把他们关进两个监狱，使得"同一监狱内最大的仇恨值"尽可能小。求这个最小值。

🔍 建模思路

第1步：二分答案。答案显然有单调性：如果"最大仇恨 ≤ W"可行，那么"最大仇恨 ≤ W'（W' > W）"一定也可行（因为限制更宽松）。所以可以二分 W。

第2步：check(W) 怎么写？把所有仇恨值 > W 的边保留下来，这些对必须被分到不同监狱。于是问题变成："把这些人分成两组，使得给定的这些边都跨越两组" —— 这正是二分图染色判定！

第3步：判定。只保留权 > W 的边，跑一次二分图染色。若能染色 → check(W) 为真（答案 ≤ W）；若出现冲突（存在奇环）→ check(W) 为假（答案 > W）。

复杂度：二分 O(log V) 次，每次染色 O(n + m)，总 O((n + m) log V)。

特别注意：图可能不连通！如果某个连通块里没有这些"必须分开"的边，它不影响判定（可以随便放）。所以染色时要跳过没有边的部分，或允许孤立块。

示例：4 名罪犯，冲突为 1-2:5、2-3:5、3-1:5、1-4:1。

· W = 4：保留权 > 4 的边 → 1-2、2-3、3-1 构成三角形（奇环）→ 染色冲突 → 不可行。

· W = 5：保留权 > 5 的边 → 没有 → 可行。

所以答案是 5。（三个人两两冲突值为 5，无论怎么分，总有两个人在同一个监狱里，他们之间的冲突值 5 就是答案。）

⚖️ "最小化最大值" + "分成两组" ⇒ 二分答案 + 二分图染色。

拓展3染色法 vs 扩展域并查集：动态加边时判奇环重要对比

问题：如果图是"一边询问一边动态加入边"，每次加边后都要问"现在有没有奇环"，二分图染色还够用吗？

🔍 两种做法的对比

染色法：每加一条边就重新染色一遍 → O(q(n + m))，边数多时会超时。

扩展域并查集（"种类并查集"）：把每个点 i 拆成两个"身份"：i（表示 i 属于第 1 类）和 i + n（表示 i 属于第 2 类）。加入边 (u,v) 时：

· 合并 u 与 v + n（u 在第 1 类 ⇒ v 必须在第 2 类）；
· 合并 v 与 u + n（对称）。

· 合并之前先检查：如果 find(u) == find(v)，说明 u、v 已经被迫同类 —— 加这条边会产生奇环。

复杂度：每次操作近似 O(α(n))，总 O(q α(n))，比重新染色快得多。

适用边界：并查集的缺点是不支持删边（所以不能做"二分答案后逐步删边"这类操作，除非用可撤销并查集或按时间分治）。而染色法对边的集合完全重新计算，天然支持"每次给定不同的边集"。

选择建议：边集固定、只问一次 → 染色法；边逐步加入、多次询问 → 扩展域并查集。

🔧 判奇环的两种武器：染色法（O(n+m)，支持任意边集）vs 扩展域并查集（O(α)，只能加边）。

③思考与启发

🤔 思考1：为什么无向图的奇点个数一定是偶数？

这个结论（"手拉手定理"）在欧拉判定里至关重要。你能证明它吗？

查看参考答案

用"数两次数"的经典论证：把所有点的度数加起来，等于 2 × 边数（因为每条边有两个端点，被两端各计一次）。所以 Σdeg(v) 一定是偶数。

把点分成"偶度点"和"奇度点"两组。偶度点的度数之和是偶数（偶数个偶数相加还是偶数）。所以 奇度点的度数之和 = 总和 − 偶度点之和 = 偶数 − 偶数 = 偶数。

而"若干个奇数相加为偶数"当且仅当这些奇数的个数是偶数。所以奇度点的个数必为偶数。

推论：奇点个数只能是 0、2、4、6…… 永远不会出现 1、3、5 —— 这也解释了为什么"欧拉通路恰好要 2 个奇点"而不是 1 个。

这道结论还有个有趣的推论：在任何一张无向图中，"能够作为一笔画起点 / 终点的点"个数只能是 0 或 2，不可能更多。

🤔 思考2：Hierholzer 为什么要"倒序输出"？不倒序会怎样？

这是初学者最常见的疑惑之一。

查看参考答案

因为压栈的顺序是"从终点到起点"。

想想最简单的例子：路径只有一条边 1→2。Hierholzer 会：从 1 走到 2；在 2 处无路可走 → 压入 2（ans = [2]）；回退到 1，1 也无路可走 → 压入 1（ans = [2, 1]）。

如果不倒序，输出就是 2 1 —— 完全反了！倒序后才得到 1 2，即正确路径。

更本质的解释：Hierholzer 的核心是 DFS 的后序。DFS 后序的性质是"最后完成的点最先被记录"，所以记录顺序天然是逆序的，必须反转。

另一种等价写法：把答案插入到队首而不是队尾（用 deque 的 push_front），这样就不需要最后反转了。

📌 一个自查技巧：如果程序输出的是"从终点到起点"的路径，就说明你忘了反转。

🤔 思考3：为什么"二分图判定"这么简单（O(n+m)），而"最大匹配"却要 O(nm)？

同是二分图上的问题，难度差异为什么这么大？

查看参考答案

因为它们本质上是两类完全不同的问题：

二分图判定是"性质检查"：只需要验证"图里有没有奇环"。染色法只需要遍历一遍图，是一次简单的、单趟的构造 —— 每一次局部决策（"邻点必须异色"）都可以立刻做出，且不会互相冲突（除非真的存在奇环）。

最大匹配是"组合优化"：要在指数级的可能方案里找最优。虽然二分图的特殊结构让它有 O(nm) 的匈牙利算法（而无一般图的匹配要更复杂），但它依然需要"反复尝试、回溯修正"（增广路）的过程，不能一次遍历就定下来。

一个有用的类比：判定二分图像"给一群人分组，只要相邻的不同组即可"（局部约束，构造容易）；最大匹配像"给一群人两两配对，要求配对数最多"（全局最优，需要搜索与调整）。

更进一步：很多"看起来是优化"的问题，在二分图上都有漂亮的等价关系，例如 König 定理（最大匹配 = 最小点覆盖）、Dilworth 定理（最长反链 = 最小链覆盖）。这些定理的价值就在于把"难问题"转化为"有现成算法的问题"。

❌ 错误

只从 1 号点开始染色，染完就返回 true。

后果：如果图不连通，其他连通块里的奇环完全没被检查到 —— 明明不是二分图却被判成二分图。

✅ 正确

外层加一个循环：for (int i = 1; i <= n; i++) if (color[i] == -1) { 从 i 开始染色 }
每个连通块都要独立检查。注意：不同连通块的颜色可以整体对调，互不影响。

口诀：染色要染满全场，每个连通块都别漏！

📋速查表

任务	判定条件 / 方法	复杂度	关键点
无向图欧拉回路	所有点 deg 为偶 + 连通	O(n+m)	孤立点忽略
无向图欧拉通路	恰 2 个奇点 + 连通	O(n+m)	起点 = 奇点
有向图欧拉回路	所有点 out == in + 弱连通	O(n+m)	不能看度数奇偶
有向图欧拉通路	恰一对 (+1, −1) + 弱连通	O(n+m)	起点 = +1 的点
求欧拉路径	Hierholzer + 倒序	O(n+m)	cur[] 当前弧优化
判连通性	答案长度 == m + 1	O(1)	最简洁的检查
字典序最小欧拉路径	邻接表排序 + Hierholzer	O((n+m) log m)	升序排序
二分图判定	染色法（BFS / DFS）	O(n+m)	每个连通块都检查
动态加边判奇环	扩展域并查集	O(q α(n))	不支持删边
二分图最大匹配	匈牙利算法（增广路）	O(nm)	König：= 最小点覆盖

题目关键词	第一步做什么	常见陷阱
"每条边走一次"	统计度数 / 出入度	忘判连通
"回到起点"	要求所有点 deg 为偶 / out == in	把回路条件用在通路上
"从哪开始走"	奇点 / out−in == 1 的点	回路时起点取编号最小的有边点
"输出方案"	Hierholzer + reverse	忘反转、递归爆栈
"字典序最小"	邻接表升序排序	排序方向反了
"分成两组"	二分图染色	只处理第一个连通块
"有矛盾不能同组"	边作为"必须异色"约束	把"至少一个"与"恰好一个"混淆
"最小化最大冲突"	二分答案 + 染色	忘记二分的单调性

📌笔记卡

🧠 必记概念

欧拉通路：每条边恰好一次；回路：还要回到起点
无向图：奇点 0（回路）或 2（通路）
有向图：out == in（回路）；恰一对 ±1（通路）
奇点个数必为偶数（手拉手定理）
二分图 ⇔ 可二染色 ⇔ 不含奇环
自环 = 长度 1 的奇环 ⇒ 非二分图
König：最大匹配 = 最小点覆盖

📐 必背模板

读边时统计：degree[u]++; degree[v]++;（无向）
或 outdeg[u]++; indeg[v]++;（有向）
奇点计数：if (degree[i] & 1) odd++;
Hierholzer：while (top) { if (有未用边) 走过去; else { ans.push(u); top--; } }
染色：color[v] = color[u] ^ 1;
冲突检测：else if (color[v] == color[u]) return false;
连通检验：ans.size() == m + 1

⚠️ 考场提醒

度数合格 ≠ 有解，必须判连通
有向图不能用度数奇偶判
Hierholzer 必须 reverse 输出
m ≥ 10⁵ 时禁用递归版
加 cur[] 当前弧优化，否则可能 O(nm)
二分图染色要遍历所有连通块
"恰好一个"（染色）≠ "至少一个"（点覆盖）
多组数据要清空 color / degree / 邻接表

课后练习

分层练习作业

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

🟢 A组 · 基础（4题）

A1概念题

欧拉通路与欧拉回路有什么区别？无向图和有向图各自的判定条件是什么？为什么"奇点个数"一定是偶数？

查看参考答案

区别：欧拉通路只要求"经过每条边恰好一次"；欧拉回路还要求起点与终点相同。所以"有回路"一定"有通路"，反之不然。

无向图判定：

· 回路：所有点度数为偶数 + 所有有边的点连通。

· 通路：恰好 2 个奇点 + 连通（这两个奇点就是起点与终点）。

有向图判定：

· 回路：所有点 outdeg == indeg + 弱连通。

· 通路：恰好一个点 outdeg − indeg = 1（起点），恰好一个点 indeg − outdeg = 1（终点），其余全相等 + 弱连通。

奇点个数必为偶数：把所有点的度数加起来等于 2 × 边数（每条边被两端各数一次），所以是偶数。偶度点的度数之和是偶数，因此奇度点的度数之和也是偶数 —— 而"若干奇数之和为偶数"要求奇数的个数是偶数。

易错：① 有向图不能用"度数奇偶"判定；② 无论哪种图，都别忘记检查连通性。

A2编程题

判定无向图能否一笔画：6 个点、7 条边，边为 1-2、1-3、2-3、3-4、4-5、5-6、6-4。请算出各点度数，判断是否有欧拉通路 / 回路，并给出起点。

查看参考答案

各点度数：

1: 连 2、3 → 2 度（偶）
2: 连 1、3 → 2 度（偶）
3: 连 1、2、4 → 3 度（奇）
4: 连 3、5、6 → 3 度（奇）
5: 连 4、6 → 2 度（偶）
6: 连 5、4 → 2 度（偶）

奇点个数 = 2（3 号点和 4 号点），且图是连通的。

结论：存在欧拉通路，不存在欧拉回路。起点必须是 3 号或 4 号（另一个为终点）。

一条合法路径：3 → 1 → 2 → 3 → 4 → 5 → 6 → 4

验证用到的边：3-1、1-2、2-3、3-4、4-5、5-6、6-4 —— 恰好全部 7 条，每条一次 ✅

注意路径上 3 号点出现了 2 次（起点和中间），4 号点出现了 2 次（中间和终点）—— 点可以重复，边不能重复。

A3判断题

判断下面说法的正误并说明理由：
（1）奇点个数为 4 的连通无向图也存在欧拉通路；
（2）有向图只要所有点 outdeg == indeg 就一定存在欧拉回路；
（3）二分图不含奇环；
（4）一个自环（u-u）会使图不再是二分图。

查看参考答案

（1）错。奇点个数只能是 0 或 2。若有 4 个奇点，说明这个图需要至少 2 笔才能画完，不存在欧拉通路（哥尼斯堡七桥就是 4 个奇点的例子）。

（2）错。还必须满足弱连通。反例：两个互不相连的环 1→2→1 和 3→4→3，每个点都满足 out == in，但一次行走无法跨过两个连通块，所以无解。这也呼应了"答案长度必须等于 m + 1"这个检验。

（3）对。这是二分图的核心等价刻画：二分图 ⇔ 不含奇环。因为染色沿环交替变化，回到起点需要偶数步。

（4）对。自环 u-u 可以看成"长度为 1 的环"，1 是奇数，所以含自环的图一定不是二分图。用染色法检查时也会直接冲突（u 与 u 相邻，必须异色，但它是同一个点）。

补充：无向图中自环对度数的贡献是 2（进和出算两次）；有向图中自环让 outdeg 和 indeg 各 +1，所以不影响欧拉判定的差值、也不需要特别处理。

A4编程题

二分图染色：6 个点、6 条边，边为 1-2、2-3、3-4、4-5、5-6、6-1。请用染色法判断是否为二分图，若是请给出两部分的划分。

查看参考答案

染色过程（从 1 号点开始，染成颜色 0）：

1 → 颜色 0
1 的邻居 2、6 → 颜色 1
2 的邻居 3 → 颜色 0
6 的邻居 5 → 颜色 0
3 的邻居 4 → 颜色 1
5 的邻居 4 → 4 已经是颜色 1，与 5 的颜色 0 不同 ✅
检查边 4-5：4 是 1、5 是 0 ✅；检查边 3-4：3 是 0、4 是 1 ✅

无冲突 ⇒ 是二分图。

划分：{1, 3, 5} 与 {2, 4, 6}

验证：1-2（0↔1）✅、2-3（1↔0）✅、3-4（0↔1）✅、4-5（1↔0）✅、5-6（0↔1）✅、6-1（1↔0）✅ —— 每条边都跨越两部分。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
int color[MAXN];
vector<int> g[MAXN];

bool bfs(int s) {
    queue<int> q; color[s] = 0; q.push(s);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : g[u]) {
            if (color[v] == -1) { color[v] = color[u] ^ 1; q.push(v); }
            else if (color[v] == color[u]) return false;
        }
    }
    return true;
}

int main(){
    int n = 6, m = 6;
    int eu[7]={0,1,2,3,4,5,6}, ev[7]={0,2,3,4,5,6,1};
    for (int i = 1; i <= m; i++) { g[eu[i]].push_back(ev[i]); g[ev[i]].push_back(eu[i]); }
    for (int i = 1; i <= n; i++) color[i] = -1;

    for (int i = 1; i <= n; i++)
        if (color[i] == -1 && !bfs(i)) { cout << "不是二分图" << endl; return 0; }

    cout << "是二分图，划分为：" << endl;
    for (int c = 0; c < 2; c++) {
        cout << "第 " << c + 1 << " 部分： ";
        for (int i = 1; i <= n; i++) if (color[i] == c) cout << i << ' ';
        cout << endl;
    }
    return 0;
}

输出：

是二分图，划分为：
第 1 部分： 1 3 5
第 2 部分： 2 4 6

易错：外层循环不能省 —— 图可能不连通，每个连通块都要独立染色检查。

🟡 B组 · 提高（4题）

B1编程题

有向图欧拉判定：5 个点、5 条边，边为 1→2、2→3、3→1、1→4、4→5。请算出度入度，判断是否存在欧拉通路 / 回路，并给出起点与终点。

查看参考答案

出度 / 入度统计：

1: out 2（→2, →4）, in 1（←3） → 差 +1
2: out 1（→3）, in 1（←1） → 差 0
3: out 1（→1）, in 1（←2） → 差 0
4: out 1（→5）, in 1（←1） → 差 0
5: out 0, in 1（←4） → 差 −1

结论：恰好一个 +1（点 1）和一个 −1（点 5），其余全为 0 ⇒ 存在欧拉通路（不是回路）。

起点 = 1，终点 = 5。

路径：1 → 2 → 3 → 1 → 4 → 5

验证：用到的边 1-2、2-3、3-1、1-4、4-5 —— 全部 5 条，每条一次 ✅

易错：① 不能只看"度数总和"的奇偶（点 1 的总度数是 3，奇数，但这不是判据）；② 起点必须是"out − in = +1"的点，也就是 1 号点，不能随随便便从别的点开始；③ 检查连通性（这里的答案是 6 个点 = 5 + 1，说明连通）。

B2编程题

Hierholzer 手动走一遍：无向图 5 个点、6 条边，边为 1-2、2-3、3-1、3-4、4-5、5-3。请写出完整的压栈过程、答案栈内容，以及最终的欧拉回路。

查看参考答案

度数：1 连 2、3 → 2 度；2 连 1、3 → 2 度；3 连 2、1、4、5 → 4 度；4 连 3、5 → 2 度；5 连 4、3 → 2 度。

全偶且连通 ⇒ 存在欧拉回路，从 1 号点出发。

走的过程：

① 1 → 2（用掉边 1-2）→ 2 → 3（用掉 2-3）→ 3 → 1（用掉 3-1）。回到 1 号点，此时 1 的所有边都用完了 → 压栈 ans = [1]，回退到 3。

② 3 号点还有未用的边 3-4 → 3 → 4 → 5（用掉 4-5）→ 5 → 3（用掉 5-3）。回到 3 号点，3 的所有边都用完了 → 压栈 ans = [1, 3]。

③ 继续回溯：5 无未用边 → ans = [1, 3, 5]；4 → [1, 3, 5, 4]；回到 3 → [1, 3, 5, 4, 3]；2 → [1, 3, 5, 4, 3, 2]；1 → [1, 3, 5, 4, 3, 2, 1]。栈的模拟结束。

答案栈：[1, 3, 5, 4, 3, 2, 1]

倒序输出（欧拉回路）：1 → 2 → 3 → 4 → 5 → 3 → 1

验证用到的边：1-2、2-3、3-4、4-5、5-3、3-1 —— 全部 6 条 ✅

关键洞察：这里正是"插环"的直观体现 —— 三角形 1-2-3-1 与三角形 3-4-5-3 在公共点 3 处被拼接成了一条完整的回路。

B3应用题

封锁阳光大学（P1330 思想）：5 个点、4 条边的无向图，边为 1-2、2-3、3-4、4-5。要求选出最少的点，使得每条边恰好有一个端点被选中。求最少点数；若不可能，输出 Impossible。

查看参考答案

第1步：判定可行性。"每条边恰好一个端点被选中"等价于"相邻两点一选一不选"，即"相邻异色" —— 就是要二分图染色。

染色：1(0) → 2(1) → 3(0) → 4(1) → 5(0)，全程无冲突 ⇒ 可行。

第2步：统计两侧人数。颜色 0：{1, 3, 5} → 3 个；颜色 1：{2, 4} → 2 个。

第3步：取较小的一侧。min(3, 2) = 2 —— 选颜色 1 的那一侧，即选中 {2, 4}。

答案：2（选 2 号和 4 号点）

验证每条边：1-2 中选了 2 ✅；2-3 中选了 2 ✅；3-4 中选了 4 ✅；4-5 中选了 4 ✅ —— 每条边恰好一个端点被选中。而且不可能只用 1 个点（因为 4 条边无法都由一个点覆盖）。

易错：① 每个连通块要独立取 min 再相加（不同连通块的颜色可以对调）；② 只处理第一个连通块就输出会漏算；③ 记得先判"是否二分图"，有奇环时输出 Impossible。

对比思考：如果题目改成"每条边至少一个端点被选中"，那就变成最小点覆盖问题，对二分图来说答案 = 最大匹配（König 定理）。"恰好一个"与"至少一个"是完全不同的问题。

B4编程题

字典序最小的欧拉路径（字母版）：给定 4 个无序字母对 `ab`、`bc`、`cd`、`de`，构造一个长度为 5 的字符串，使得每个字母对都恰好相邻出现一次，要求字典序最小。

查看参考答案

第1步：建图。字母 a~e 作为点，每个字母对作为一条无向边：a-b、b-c、c-d、d-e（一条链 a-b-c-d-e）。

第2步：算度数。a:1（奇）、b:2、c:2、d:2、e:1（奇） → 恰好 2 个奇点（a 和 e）。

第3步：确定起点。必须从奇点出发，两个奇点是 a 和 e，取字典序较小的 —— 起点 = a。

第4步：Hierholzer。唯一的走法是 a → b → c → d → e，答案栈为 [e, d, c, b, a]，倒序输出得 a b c d e。

答案：abcde

换个例子（全是偶点）：若输入为 ab、bc、cd、da（一个 4 环 a-b-c-d-a），所有点度数为 2（全偶）⇒ 存在欧拉回路。起点取字典序最小的有边点 a，邻接表升序排列后 Hierholzer 得到答案 "abcda"（另一条合法串 "acbda" 更大）。

易错：① 字母区分大小写（'A' ≠ 'a'）；② 起点的选取要同时满足"奇点优先"和"字典序最小"；③ 输出的是字符串而不是空格分隔的数字；④ 存在自环（如 aa）时度数 +2。

🔴 C组 · 挑战（4题）

C1综合题

关押罪犯（P1525 思想）：4 名罪犯，冲突为 1-2:5、2-3:5、3-1:5、1-4:1。要把他们分到两所监狱，使"同一监狱内最大的冲突值"尽可能小。求这个最小值，并说明算法。

查看参考答案

思路：二分答案 + 二分图染色。

单调性：若"最大冲突 ≤ W"可行，则"最大冲突 ≤ W′"（W′ > W）也可行（限制更宽松）→ 可以二分。

check(W)：把所有冲突值 > W 的边保留，这些对必须分到不同监狱。判断"保留的图是否为二分图" —— 是则 check(W) 为真。

逐步检验：

· W = 4：保留权 > 4 的边 → 1-2(5)、2-3(5)、3-1(5)，构成三角形（奇环）→ 染色冲突 → 不可行。

· W = 5：保留权 > 5 的边 → 一条都没有 → 空图是二分图 → 可行。

答案：5

直观解释：1、2、3 两两之间的冲突值都是 5，一共只有两所监狱，根据抽屉原理，这三个人里必有两人在同一个监狱 → 他们之间的冲突值 5 必然发生；而把 1、4（冲突 1）分开就能让最大值不超过 5。所以最小值是 5。

复杂度：二分 O(log V) 次 × 每次染色 O(n + m) = O((n + m) log V)。

易错：① 图可能不连通，染色时要跳过没有"必须分开"边的部分；② check 的方向别写反（保留 > W 的边，不是 ≤ W）；③ 二分边界的处理（本题答案可能为 0，表示所有冲突都能被分开）。

C2思维题

动态加边判奇环：一张图初始没有边，接下来有 q 次操作，每次加入一条边 (u, v)，要求在每次加入后立刻回答"当前图中是否存在奇环"。请给出比"每次重新染色"更快的方法。

查看参考答案

方法：扩展域并查集（种类并查集）。

核心思想：把每个点 i 拆成两个"身份"：i 表示"i 属于第 1 类"，i + n 表示"i 属于第 2 类"。等价关系就是"这两个身份必须在同一侧"。

加入边 (u, v) 时：

① 先检查：若 find(u) == find(v)，说明 u 与 v 已经被迫同类（因为之前的约束要求它们同色），此时加入边 (u,v) 会产生奇环 → 输出"有奇环"。

② 否则合并：union(u, v + n) 与 union(v, u + n) —— 含义是"u 若在第 1 类，则 v 必须在第 2 类"，反之亦然。

为什么正确："偶数条边的路径"会把两点约束到同一类，"奇数条边的路径"约束到不同类。并查集恰好维护了这种"奇偶性"的等价关系；一旦发现在一个连通块内部出现了奇偶矛盾，就说明有奇环。

复杂度：每次操作近似 O(α(n))，总 O(q α(n))；而"每次重新染色"是 O(q(n + m))，边多时会超时。

对比总结：

· 染色法：O(n+m)，支持"任意给定边集"（每次可以换一批边），但不能增量更新。

· 扩展域并查集：O(α)，只能加边不能删边，但增量查询极快。

· 线段树分治 + 可撤销并查集：同时支持加边与删边，O((n+m) log m α)，这是更高级的技巧（线下分治）。

C3综合题

二分图最大匹配：左边 3 个学生 S1、S2、S3，右边 3 个项目 P1、P2、P3。可选关系为 S1→{P1, P2}、S2→{P1}、S3→{P2, P3}。求最大匹配的大小，并说明"增广路"的作用。

查看参考答案

答案：最大匹配 = 3，一个最优配对是 S1-P2、S2-P1、S3-P3。

匈牙利算法的求解过程：

①为 S1 找对象：尝试 P1（未匹配）→ 配对成功。match = {S1-P1}。

②为 S2 找对象：S2 只能选 P1，但 P1 已被 S1 占用 → 尝试给 S1 换一个对象：S1 还可以选 P2，而 P2 未匹配 → 让 S1 改配 P2，S2 配 P1。match = {S1-P2, S2-P1}。这个"重新安排旧配对"的过程就是增广。

③为 S3 找对象：S3 可选的 P2、P3 中 P2 被 S1 占、P3 空闲 → 直接配 P3。match = {S1-P2, S2-P1, S3-P3}，大小为 3。

增广路的本质：一条"未匹配边 → 匹配边 → 未匹配边 → … → 未匹配边"的交替路径。把这条路径上的匹配状态全部取反（未匹配变匹配、匹配变未匹配），匹配数就 +1。匈牙利算法就是不断找增广路直到找不到为止（此时由 Berge 定理可知已是最大匹配）。

复杂度：O(n × m)（每个左部点跑一次 DFS/BFS）。

易错：① 每次为新的左部点找对象时，visited 数组要清空（保证本次搜索每条边只走一次）；② dfs 里"递归给旧配对换对象"这一步不能漏，否则得到的是"贪心匹配"而不是"最大匹配"。

拓展定理（König）：二分图中，最大匹配的大小 = 最小点覆盖的大小。所以"每条边至少选一个端点，最少选几个点"这个问题，答案就是最大匹配。

C4思维题

综合思考：为什么"欧拉问题"（走遍所有边）有 O(n+m) 的算法，而"哈密顿问题"（走遍所有点）却是 NP 难？谈谈你的理解。

查看参考答案

关键在于"局部约束"与"全局约束"的区别。

欧拉问题的约束是局部的：每经过一个点，"进一条边、出一条边"，这个约束只涉及该点自己的度数。走每一步时，只要"当前点还有未使用的边"就可以继续走。Hierholzer 之所以正确，是因为它可以把"走不完"这种情况完全归结为"图不连通"这个一次性的全局检查。整个过程只需要 O(n+m) 的遍历。

哈密顿问题的约束是全局的：要求"每个点恰好访问一次"，这意味着当你选择下一步时，必须考虑"剩下的点还能不能被访问到"，任何一次局部选择都可能让全局无解。这种"当前决策依赖于全局状态"的结构正是 NP 难问题的典型特征 —— 目前没有已知的多项式算法（并且普遍认为不存在）。

一个更本质的类比：

· 欧拉问题：有点像"把所有的珠子串成一条项链"，只关心珠子之间的连接（边）；
· 哈密顿问题：有点像"给一群人排一个座位表，每个人只能坐一次且认识相邻的人"，需要同时满足所有点。

对竞赛的启示：看到"每条边走一次"就可以放心地建图跑欧拉；看到"每个点恰好一次"，要先判断数据范围 —— 如果 n ≤ 20 可能是状压 DP（O(2ⁿ n²)），如果 n 很大就要考虑题目是不是有特殊结构（例如 DAG、树的延伸、或者根本不是要求哈密顿路径）。

🌟 这也是图论里一个非常有意思的现象：一对看起来相似的问题（点和边的区别），复杂度可能相差一个数量级 —— 从多项式到 NP 难。建模时一定要把"约束对象"看清楚。

🔵 洛谷原题精选（12 道）

按难度从易到难排序，建议先做题号 1~6（欧拉路径与二分图判定），再攻 7~12（匹配与综合建模）。

P7771
【模板】欧拉路径入门

P1330
封锁阳光大学普及

P2731
[USACO3.3] 骑马修栅栏 Riding the Fences普及

P1127
词链普及

P1341
无序字母对普及

P6066
[USACO05JAN] Watchcow S普及

P3386
【模板】二分图最大匹配提高

P2756
飞行员配对方案问题提高

P1525
[NOIP2010 提高组] 关押罪犯提高

P1155
[NOIP2008 提高组] 双栈排序提高

P1640
[SCOI2010] 连续攻击游戏提高

P1129
[ZJOI2007] 矩阵游戏提高

情景导航

一笔画

扫雪车路线

分成两队拔河

排课表

知识探究

这就是"插环"的直观图景

🔄 递归版（更简洁但有风险）

⚡ 当前弧优化（cur 数组）

染色过程（对应左侧图）

💡 想一想

💡 想一想

💡 想一想

实践应用

一笔画判定：判断下面三张图能否一笔画（走遍每条边恰好一次）。（甲）5 个点，边为 1-2、2-3、3-1、1-4、4-5、5-1；（乙）4 个点，边为 1-2、2-3、3-1、3-4；（丙）5 个点，边为 1-2、2-3、3-4、4-5、1-3。

二分图染色：判断下面两张图是否为二分图，若是请给出两部分的划分。（甲）6 个点，边为 1-2、2-3、3-4、4-5、5-6、6-1；（乙）4 个点，边为 1-2、2-3、3-4、4-1、1-3。

欧拉路径构造：有向图 5 个点、6 条边，边为 1→2、2→3、3→1、1→4、4→5、5→1。请判定并给出字典序最小的欧拉路径（用 Hierholzer 手动走一遍）。

总结提升

🤔 思考1：为什么无向图的奇点个数一定是偶数？

🤔 思考2：Hierholzer 为什么要"倒序输出"？不倒序会怎样？

🤔 思考3：为什么"二分图判定"这么简单（O(n+m)），而"最大匹配"却要 O(nm)？

学习检测

只看度数条件，忘记判连通性

用"度数奇偶"判断有向图

Hierholzer 忘记倒序输出

递归版 Hierholzer 爆栈

二分图染色时只处理了一个连通块

🧠 必记概念

📐 必背模板

⚠️ 考场提醒

分层练习作业

🟢 A组 · 基础（4题）

欧拉通路与欧拉回路有什么区别？无向图和有向图各自的判定条件是什么？为什么"奇点个数"一定是偶数？

判定无向图能否一笔画：6 个点、7 条边，边为 1-2、1-3、2-3、3-4、4-5、5-6、6-4。请算出各点度数，判断是否有欧拉通路 / 回路，并给出起点。

判断下面说法的正误并说明理由：（1）奇点个数为 4 的连通无向图也存在欧拉通路；（2）有向图只要所有点 outdeg == indeg 就一定存在欧拉回路；（3）二分图不含奇环；（4）一个自环（u-u）会使图不再是二分图。

二分图染色：6 个点、6 条边，边为 1-2、2-3、3-4、4-5、5-6、6-1。请用染色法判断是否为二分图，若是请给出两部分的划分。

🟡 B组 · 提高（4题）

有向图欧拉判定：5 个点、5 条边，边为 1→2、2→3、3→1、1→4、4→5。请算出度入度，判断是否存在欧拉通路 / 回路，并给出起点与终点。

Hierholzer 手动走一遍：无向图 5 个点、6 条边，边为 1-2、2-3、3-1、3-4、4-5、5-3。请写出完整的压栈过程、答案栈内容，以及最终的欧拉回路。

封锁阳光大学（P1330 思想）：5 个点、4 条边的无向图，边为 1-2、2-3、3-4、4-5。要求选出最少的点，使得每条边恰好有一个端点被选中。求最少点数；若不可能，输出 Impossible。

字典序最小的欧拉路径（字母版）：给定 4 个无序字母对 ab、bc、cd、de，构造一个长度为 5 的字符串，使得每个字母对都恰好相邻出现一次，要求字典序最小。

🔴 C组 · 挑战（4题）

关押罪犯（P1525 思想）：4 名罪犯，冲突为 1-2:5、2-3:5、3-1:5、1-4:1。要把他们分到两所监狱，使"同一监狱内最大的冲突值"尽可能小。求这个最小值，并说明算法。

动态加边判奇环：一张图初始没有边，接下来有 q 次操作，每次加入一条边 (u, v)，要求在每次加入后立刻回答"当前图中是否存在奇环"。请给出比"每次重新染色"更快的方法。

二分图最大匹配：左边 3 个学生 S1、S2、S3，右边 3 个项目 P1、P2、P3。可选关系为 S1→{P1, P2}、S2→{P1}、S3→{P2, P3}。求最大匹配的大小，并说明"增广路"的作用。

综合思考：为什么"欧拉问题"（走遍所有边）有 O(n+m) 的算法，而"哈密顿问题"（走遍所有点）却是 NP 难？谈谈你的理解。

🔵 洛谷原题精选（12 道）

判断下面说法的正误并说明理由：
（1）奇点个数为 4 的连通无向图也存在欧拉通路；
（2）有向图只要所有点 outdeg == indeg 就一定存在欧拉回路；
（3）二分图不含奇环；
（4）一个自环（u-u）会使图不再是二分图。

字典序最小的欧拉路径（字母版）：给定 4 个无序字母对 `ab`、`bc`、`cd`、`de`，构造一个长度为 5 的字符串，使得每个字母对都恰好相邻出现一次，要求字典序最小。