科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载导读本文以 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也必定是偶数。因此把度数为奇数的节点记入集合oddm |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]分两种情况x 与 y 之间没有边直接添加一条边(x, y)两个奇度节点同时变成偶度其余节点度数不变符合要求返回true。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]。此时需要添加两条边把四个奇度节点两两配对每对之间连一条边四个节点的度数就都变回偶数。共有三种配对方式(a, b)与(c, d)(a, c)与(b, d)(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分类判断。Python3class 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 FalseJavaclass Solution { public boolean isPossible(int n, ListListInteger edges) { var g new Set[n 1]; Arrays.setAll(g, e - new HashSetInteger()); for (var e : edges) { int x e.get(0), y e.get(1); g[x].add(y); g[y].add(x); } var odd new ArrayListInteger(); 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; } }Cclass Solution { public: bool isPossible(int n, vectorvectorint edges) { unordered_setint g[n 1]; for (auto e : edges) { int x e[0], y e[1]; g[x].insert(y); g[y].insert(x); } vectorint 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中的三个用例可以完整走一遍分类讨论的分支用例输入分类走向结果1n5边[[1,2],[2,3],[3,4],[4,2],[1,4],[2,5]]度数 4 为 3、5 为 1odd{4,5}m2且 4、5 之间无边直接连(4,5)true2n4边[[1,2],[3,4]]四个节点度数全为 1odd{1,2,3,4}m4配对(1,3)(2,4)均无现成边true3n4边[[1,2],[1,3],[1,4]]节点 1 度数为 3其余为 1odd{1,2,3,4}m4三种配对都至少包含一条已有边无解false第 3 个用例正是 m 4 分支的典型反例星形图中心节点 1 已与 2、3、4 全部相连无论哪两种配对都会撞上已存在的边因而无法加边验证了三种配对全部失败即返回 false的必要性。复杂度分析时间复杂度O(n m)其中m为edges的长度。建图与统计奇度节点各需一次线性扫描m 2 时最坏情况下遍历[1, n]全部节点一次仍为线性。空间复杂度O(n m)用于存储邻接集合g与奇度集合odd。小结一类度数奇偶性 有限加边题目的通用套路本题的解法具有很好的迁移性其分析链条可以总结为四步通用框架用握手定理确认奇数度节点个数m必为偶数排除m ≥ 2k2的大规模无解情形k为可加边数上限本题k 2把加边看作奇偶性翻转一条边翻转两个端点的奇偶性由此确定每条新边必须命中至少一个奇度节点按 m 的取值分类讨论m 0 直接成功、m 2 要么一条直连要么找偶度中介连两条、m 4 则枚举三种配对补全边界检查不允许重复加边、不允许自环是每步判断无边的前提。仓库中同场次的其余题目a.go 的字符掩码计数、b.go 的质因数分解迭代、d.go 的完全二叉树环长查询与本题共同展示了对图论/数论结构做精细分类讨论的周赛解题风格而 c.go 与 c_test.go 则展示了算法竞赛代码如何在仓库中以源码 数据文件 反射驱动测试的方式沉淀与回归验证。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐codeforces-go 题解LeetCode 第 112 场双周赛「通过操作使字符串相等 II」的奇偶分组计数法codeforces go 题解LeetCode 第 112 场双周赛「通过操作使字符串相等 II」的奇偶分组计数法 本篇以 codeforces go 仓库科学计算LeetCode 324 摆动排序 II 题解倒序排序 奇偶索引分置的构造法LeetCode 324 摆动排序 II 题解倒序排序 奇偶索引分置的构造法 导读 本题是 LeetCode 324「摆动排序 II」属于典型的 构造类文档教程知识库AnimatedDrawings 实用指南把手绘小人做成可导出的动画 GIFAnimatedDrawings 实用指南把手绘小人做成可导出的动画 GIF 孩子纸上画了个小人你想看这个小人跳舞用 AnimatedDrawings 就科学计算上一篇GhostNetV2模型安全指南如何保护你的AI模型不被攻击下一篇ReClip高清视频怎么选4K/1080p/720p选择指南与体积对比全解创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考