企业官网建设流程全解析

• 科学计算

导读

本文以 codeforces-go 仓库中 LeetCode 周赛 324 第三题（Add Edges to Make Degrees of All Nodes Even）的题解笔记（leetcode/weekly/324/c/README.md）为主体，完整讲解"至多添加两条边使无向图所有节点度数变为偶数"的奇偶度分类构造法：利用握手定理把问题规约为对奇数度节点的分类讨论（m = 0、2、4），并给出 Python、Java、C++、Go 四种语言的完整实现、正确性论证、复杂度分析，以及仓库内 Go 源码与本地测试用例的验证全过程。读完本文，你将掌握这类"度数奇偶性 + 有限次加边构造"题目的通用分析框架。

题目问题重述

给定一个无向图，共有n个节点，编号为1到n，初始边集为edges。只允许添加至多两条边（新加的边不能与已有边重复，也不能是自环），判断是否存在一种加边方案，使得添加后图中每一个节点的度数都变成偶数。

这个问题看似需要枚举加边组合，但借助图论中的基本事实，可以将其化归为对"奇数度节点集合"的简单分类讨论。

核心洞察：握手定理与奇度节点的奇偶性

设deg(i)表示节点i的度数。根据握手定理，无向图中所有节点度数之和等于边数的两倍，必然为偶数：

deg(1) + deg(2) + … + deg(n) = 2 × |E|

由于等式右边是偶数，左边各度数中奇数的个数m也必定是偶数。因此：

• 把度数为奇数的节点记入集合odd，m = |odd|只可能是 0、2、4、6、…；
• 每添加一条边(u, v)，只会同时改变u、v两个节点的度数奇偶性（各翻转一次，±1）。

由以上两点可以立刻排除大部分情况：若m ≥ 6，由于至多添加两条边，最多只能翻转 4 个节点的奇偶性，永远无法把所有m个奇度节点全部修正为偶度，直接返回false。于是真正需要分析的只有m = 0、m = 2、m = 4三种情形。这里odd只统计有边节点（出现在edges中的节点），孤立的节点度数为 0，是偶数，无需处理。

分类讨论：m = 0 / 2 / 4

情形一：m = 0，无需加边

没有任何奇数度节点，图已经符合要求，直接返回true。

情形二：m = 2，两个奇度节点 x、y

记x = odd[0]、y = odd[1]，分两种情况：

1. x 与 y 之间没有边：直接添加一条边(x, y)，两个奇度节点同时变成偶度，其余节点度数不变，符合要求，返回true。
2. x 与 y 之间已经有边：不能再重复加这条边。此时必须添加两条边，且两条边都必须"消耗"奇度节点。由于仅剩 x、y 两个奇度节点，合理方案是找一个节点i作为"中介"，同时连(x, i)与(y, i)：
   • i不在odd中，所以deg(i)是偶数，加两条边后变为deg(i) + 2，依然是偶数；
   • x、y各加一条边，由奇变偶。
   • 前提是i与 x、y 之间都没有边（否则重复加边非法），且i不能等于 x、y 本身。
   • 于是枚举[1, n]中所有不为 x、y 的点，只要存在i使得(i, x)与(i, y)均不存在，就返回true；否则返回false。

为什么 m = 2 且已有边时只能走"中介"方案？因为两条边若都连在两个偶度节点之间，会把它们变成奇度节点，得不偿失；若与 x 或 y 重复相连则非法。所以唯一可行的两条边结构就是(x, i)、(y, i)，这与枚举逻辑完全对应。

情形三：m = 4，四个奇度节点 a、b、c、d

记a, b, c, d = odd[0..3]。此时需要添加两条边，把四个奇度节点两两配对，每对之间连一条边，四个节点的度数就都变回偶数。共有三种配对方式：

1. (a, b)与(c, d)
2. (a, c)与(b, d)
3. (a, d)与(b, c)

只要某一组配对中的两条边都没有出现在原图中（不允许重复加边），即可返回true；三种配对都行不通则返回false。

return (b∉adj[a] 且 d∉adj[c]) // 配对 1 或 (c∉adj[a] 且 d∉adj[b]) // 配对 2 或 (d∉adj[a] 且 c∉adj[b]) // 配对 3

其余情形（m ≥ 6）

如前所述，两条边最多修正 4 个奇度节点，m ≥ 6时必然无解，返回false。至此分类讨论完整闭合。

多语言参考实现

以下代码原样继承自题解笔记（leetcode/weekly/324/c/README.md），四种语言的逻辑完全一致，均采用邻接集合表示图、遍历节点统计奇度集合、再按m分类判断。

Python3

class Solution: def isPossible(self, n: int, edges: List[List[int]]) -> bool: g = defaultdict(set) for x, y in edges: g[x].add(y) g[y].add(x) odd = [i for i, nb in g.items() if len(nb) % 2] m = len(odd) if m == 0: return True if m == 2: x, y = odd return x not in g[y] or any( i != x and i != y and x not in g[i] and y not in g[i] for i in range(1, n + 1)) if m == 4: a, b, c, d = odd return b not in g[a] and d not in g[c] or \ c not in g[a] and d not in g[b] or \ d not in g[a] and c not in g[b] return False

Java

class Solution { public boolean isPossible(int n, List<List<Integer>> edges) { var g = new Set[n + 1]; Arrays.setAll(g, e -> new HashSet<Integer>()); for (var e : edges) { int x = e.get(0), y = e.get(1); g[x].add(y); g[y].add(x); } var odd = new ArrayList<Integer>(); for (var i = 1; i <= n; ++i) if (g[i].size() % 2 > 0) odd.add(i); var m = odd.size(); if (m == 0) return true; if (m == 2) { int x = odd.get(0), y = odd.get(1); if (!g[x].contains(y)) return true; for (var i = 1; i <= n; ++i) if (i != x && i != y && !g[i].contains(x) && !g[i].contains(y)) return true; return false; } if (m == 4) { int a = odd.get(0), b = odd.get(1), c = odd.get(2), d = odd.get(3); return !g[a].contains(b) && !g[c].contains(d) || !g[a].contains(c) && !g[b].contains(d) || !g[a].contains(d) && !g[b].contains(c); } return false; } }

C++

class Solution { public: bool isPossible(int n, vector<vector<int>> &edges) { unordered_set<int> g[n + 1]; for (auto &e : edges) { int x = e[0], y = e[1]; g[x].insert(y); g[y].insert(x); } vector<int> odd; for (int i = 1; i <= n; ++i) if (g[i].size() % 2) odd.push_back(i); int m = odd.size(); if (m == 0) return true; if (m == 2) { int x = odd[0], y = odd[1]; if (!g[x].count(y)) return true; for (int i = 1; i <= n; ++i) if (i != x && i != y && !g[i].count(x) && !g[i].count(y)) return true; return false; } if (m == 4) { int a = odd[0], b = odd[1], c = odd[2], d = odd[3]; return !g[a].count(b) && !g[c].count(d) || !g[a].count(c) && !g[b].count(d) || !g[a].count(d) && !g[b].count(c); } return false; } };

Go（仓库同款实现）

仓库中的正式实现位于 leetcode/weekly/324/c/c.go，用map[int]map[int]bool构建邻接集合：

func isPossible(n int, edges [][]int) bool { g := map[int]map[int]bool{} for _, e := range edges { x, y := e[0], e[1] if g[x] == nil { g[x] = map[int]bool{} } g[x][y] = true if g[y] == nil { g[y] = map[int]bool{} } g[y][x] = true } odd := []int{} for i, nb := range g { if len(nb)%2 > 0 { odd = append(odd, i) } } m := len(odd) if m == 0 { return true } if m == 2 { x, y := odd[0], odd[1] if !g[x][y] { return true } for i := 1; i <= n; i++ { if i != x && i != y && !g[i][x] && !g[i][y] { return true } } return false } if m == 4 { a, b, c, d := odd[0], odd[1], odd[2], odd[3] return !g[a][b] && !g[c][d] || !g[a][c] && !g[b][d] || !g[a][d] && !g[b][c] } return false }

值得注意的 Go 实现细节：!g[x][y]在x不在g中时会读取nilmap 的键，Go 对nilmap 的读取返回零值false，因此不存在越界或 panic 风险，天然满足"无边即返回 true"的语义。另外，odd的收集只需遍历g（有边节点），而 m = 2 情形中枚举中介点i时需要覆盖[1, n]的全部节点——包括孤立节点，因为孤立点度数恒为 0（偶数），完全有资格充当中介，这一枚举范围正是分类讨论正确性的关键一环。

仓库内的测试验证

在讲解算法之外，仓库还提供了一套完整的本地测试链路，可用于亲手验证实现：

• 测试入口 leetcode/weekly/324/c/c_test.go 调用testutil.RunLeetCodeFuncWithFile(t, isPossible, "c.txt", targetCaseNum)，从文本文件按组读取输入输出；
• 用例文件 leetcode/weekly/324/c/c.txt 以"函数入参 + 期望输出"分组存放，其解析逻辑位于 leetcode/testutil/leetcode.go：先剔除空行，再利用反射获取函数的入参/出参个数fNumIn、fNumOut，按fNumIn + fNumOut行一组切分成用例，最终逐个断言输出。

用c.txt中的三个用例可以完整走一遍分类讨论的分支：

第 3 个用例正是 m = 4 分支的典型反例：星形图中心节点 1 已与 2、3、4 全部相连，无论哪两种配对都会撞上已存在的边，因而无法加边，验证了"三种配对全部失败即返回 false"的必要性。

复杂度分析

• 时间复杂度：O(n + m)，其中m为edges的长度。建图与统计奇度节点各需一次线性扫描；m = 2 时最坏情况下遍历[1, n]全部节点一次，仍为线性。
• 空间复杂度：O(n + m)，用于存储邻接集合g与奇度集合odd。

小结：一类"度数奇偶性 + 有限加边"题目的通用套路

本题的解法具有很好的迁移性，其分析链条可以总结为四步通用框架：

1. 用握手定理确认奇数度节点个数m必为偶数，排除m ≥ 2k+2的大规模无解情形（k为可加边数上限，本题k = 2）；
2. 把加边看作奇偶性翻转：一条边翻转两个端点的奇偶性，由此确定每条新边必须"命中"至少一个奇度节点；
3. 按 m 的取值分类讨论：m = 0 直接成功、m = 2 要么一条直连要么找偶度中介连两条、m = 4 则枚举三种配对；
4. 补全边界检查：不允许重复加边、不允许自环，是每步判断"无边"的前提。

仓库中同场次的其余题目（a.go 的字符掩码计数、b.go 的质因数分解迭代、d.go 的完全二叉树环长查询）与本题共同展示了"对图论/数论结构做精细分类讨论"的周赛解题风格，而 c.go 与 c_test.go 则展示了算法竞赛代码如何在仓库中以"源码 + 数据文件 + 反射驱动测试"的方式沉淀与回归验证。

• 科学计算