科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇文章以 codeforces-go 仓库中 leetcode/biweekly/181/c/README.md 这一力扣双周赛 181 Q3 题解为主体完整剖析「统计和为偶数的连通子图数量Count Connected Subgraphs with Even Node Sum」这道题的两种解法朴素 DFS 二进制枚举与位运算 BFS 优化并结合仓库中的 Go 实现、测试框架与位运算模板给出可直接复用的实战方案。读完你将掌握「用二进制数表示集合、枚举子集、判断子图连通性」这一整套高频算法套路并能将其迁移到 $n \le 13 \sim 20$ 量级的子集型枚举问题中。题目与核心思路题目给定长度为 $n$ 的 01 数组nums节点权值只有 0 和 1与无向图边集edges要求统计满足以下两个条件的非空子图即节点的子集及其内部边数量子图中所有节点的权值之和为偶数该子图是连通的任意选两个在子图中的节点都存在只经过子图内节点的路径。关键突破口是数据范围$n \le 13$。于是可以直接枚举节点集合 $U {0,1,2,...,n-1}$ 的所有非空子集 $S$数量只有 $2^n - 1 \le 8191$ 个完全可以在 $\mathcal{O}(2^n \cdot (nm))$ 的时间复杂度内穷举完。对于每个 $S$若其节点值总和是偶数且 $S$ 连通则答案增加一否则跳过。如何判断 $S$ 是否连通随便选一个在 $S$ 中的节点作为 DFS 起点在 DFS 这张图的过程中只访问在 $S$ 中的节点DFS 结束后如果访问过的节点集合恰好等于 $S$说明 $S$ 是连通的。这个思路可以进一步利用位运算压成 $\mathcal{O}(1)$ 级别的集合判断见下文方法二。两个关键技巧代码实现时文档给出两条核心技巧偶数判定的等价变形由于节点值只有 $0$ 和 $1$节点值之和是偶数等价于节点值的异或和为 0奇数个 1 异或结果为 1偶数个 1 异或结果为 0这为后续位运算优化埋下伏笔。用二进制表示集合一个整数sub的第 $i$ 位为 1 表示节点 $i$ 属于该集合集合的交并补、元素判定全部可以落到位运算上如sub i 1判断 $i$ 是否在sub中。这一技巧的分类总结可参考仓库模板库 copypasta/bits.go 中关于 lowbit、isSubset、isPow2等集合操作的封装copypasta/bits.go。方法一朴素 DFS 二进制枚举四种语言实现原文档为每种语言给出了完整可运行的代码这里全部保留并以 Go 版本为主线逐行解读。Pythonclass Solution: def evenSumSubgraphs(self, nums: list[int], edges: list[list[int]]) - int: n len(nums) g [[] for _ in range(n)] for x, y in edges: g[x].append(y) g[y].append(x) # 枚举节点集合 U {0,1,2,...,n-1} 的非空子集 sub u (1 n) - 1 ans 0 for sub in range(1, u 1): # 计算子图的点权异或和 xor_sum 0 for i, x in enumerate(nums): if sub i 1: # i 在 sub 中 xor_sum ^ x if xor_sum: continue def dfs(x: int) - None: nonlocal vis vis | 1 x # 标记 x 已访问 for y in g[x]: if (vis y 1) 0: # y 没有访问过 dfs(y) # 判断子图是否连通 vis u ^ sub # 技巧把不在子图中的节点都标记为已访问 dfs(sub.bit_length() - 1) # 随便选一个在子图中的节点开始 DFS if vis u: # 所有节点都已访问子图是连通的 ans 1 return ansJavaclass Solution { private int vis; public int evenSumSubgraphs(int[] nums, int[][] edges) { int n nums.length; ListInteger[] g new ArrayList[n]; Arrays.setAll(g, _ - new ArrayList()); for (int[] e : edges) { int x e[0]; int y e[1]; g[x].add(y); g[y].add(x); } // 枚举节点集合 U {0,1,2,...,n-1} 的非空子集 sub int u (1 n) - 1; int ans 0; for (int sub 1; sub u; sub) { // 计算子图的点权异或和 int xor 0; for (int i 0; i n; i) { if ((sub i 1) 0) { // i 在 sub 中 xor ^ nums[i]; } } if (xor ! 0) { continue; } // 判断子图是否连通 vis u ^ sub; // 技巧把不在子图中的节点都标记为已访问 dfs(Integer.numberOfTrailingZeros(sub), g); if (vis u) { // 所有节点都已访问子图是连通的 ans; } } return ans; } private void dfs(int x, ListInteger[] g) { vis | 1 x; // 标记 x 已访问 for (int y : g[x]) { if ((vis y 1) 0) { // y 没有访问过 dfs(y, g); } } } }Cclass Solution { public: int evenSumSubgraphs(vectorint nums, vectorvectorint edges) { int n nums.size(); vectorvectorint g(n); for (auto e : edges) { int x e[0], y e[1]; g[x].push_back(y); g[y].push_back(x); } // 枚举节点集合 U {0,1,2,...,n-1} 的非空子集 sub int u (1 n) - 1; int ans 0; for (int sub 1; sub u; sub) { // 计算子图的点权异或和 int xor_sum 0; for (int i 0; i n; i) { if (sub i 1) { // i 在 sub 中 xor_sum ^ nums[i]; } } if (xor_sum) { continue; } // 判断子图是否连通 int vis u ^ sub; // 技巧把不在子图中的节点都标记为已访问 auto dfs - void { vis | 1 x; // 标记 x 已访问 for (int y : g[x]) { if ((vis y 1) 0) { // y 没有访问过 dfs(y); } } }; dfs(countr_zero((uint32_t) sub)); // 随便选一个在子图中的节点开始 DFS ans vis u; // 所有节点都已访问子图是连通的 } return ans; } };Gofunc evenSumSubgraphs(nums []int, edges [][]int) (ans int) { n : len(nums) g : make([][]int, n) for _, e : range edges { x, y : e[0], e[1] g[x] append(g[x], y) g[y] append(g[y], x) } // 枚举节点集合 U {0,1,2,...,n-1} 的非空子集 sub u : 1n - 1 for sub : 1; sub u; sub { // 计算子图的点权异或和 xor : 0 for i, x : range nums { if subi1 0 { // i 在 sub 中 xor ^ x } } if xor ! 0 { continue } // 判断子图是否连通 vis : u ^ sub // 技巧把不在子图中的节点都标记为已访问 var dfs func(int) dfs func(x int) { vis | 1 x // 标记 x 已访问 for _, y : range g[x] { if visy1 0 { // y 没有访问过 dfs(y) } } } dfs(bits.TrailingZeros(uint(sub))) // 随便选一个在子图中的节点开始 DFS if vis u { // 所有节点都已访问子图是连通的 ans } } return }逐行要点解读建图把无向边(x, y)双向加入邻接表g。起点选取dfs(sub.bit_length() - 1)Java 用Integer.numberOfTrailingZeros(sub)Go 用bits.TrailingZeros(uint(sub))C 用countr_zero取的是sub中最右侧最低位那个 1 所在的位置也就是随便选一个在 $S$ 中的节点三行代码等价。vis u ^ sub的精妙之处$U$ 的全集掩码是uu ^ sub恰好等于u - sub因为sub ⊆ u结果是一个把不在子图中的所有节点都置为已访问的初始掩码。这样一来 DFS 过程中根本无需显式判断是否在子图内——不在子图中的节点天然不可能被再次访问只需在vis上做并集即可。连通判定DFS 结束后若vis u说明子图内节点全部可达子图连通ans。复杂度分析时间复杂度$\mathcal{O}(2^n(nm))$其中 $n$ 是nums的长度$m$ 是edges的长度。每次 DFS 需要 $\mathcal{O}(nm)$ 的时间。空间复杂度$\mathcal{O}(nm)$。方法二位运算 BFS 优化朴素做法中每个子集都要用 $\mathcal{O}(n)$ 计算点权和、用 $\mathcal{O}(nm)$ 做 DFS。原文档给出三步优化把总复杂度压到 $\mathcal{O}(m n2^n)$压缩点权既然nums只有 $0$ 和 $1$可以将其压缩成一个二进制数ones第 $i$ 位为 1 表示节点 $i$ 的权值为 1这样可以用 $\mathcal{O}(1)$ 的popcount(sub ones)计算子集的点权和压缩邻接表用二进制数保存 $g$ 的邻居节点$g[x]$ 的第 $y$ 位为 1 表示存在边 $(x, y)$位运算 BFS把 DFS 换成BFS用一个二进制数q代替队列表示当前在队列中的节点集合。原文档特别注明严格来说这不是 BFS只是遍历图的一种方法——队列中任意节点出队时一次性把全部未访问邻居入队本质上仍是集合层面的图遍历。四种语言实现如下Pythonclass Solution: def evenSumSubgraphs(self, nums: list[int], edges: list[list[int]]) - int: n len(nums) g [0] * n for x, y in edges: g[x] | 1 y g[y] | 1 x ones 0 for i, x in enumerate(nums): ones | x i # 枚举节点集合 U {0,1,2,...,n-1} 的非空子集 sub u (1 n) - 1 ans 0 for sub in range(1, u 1): # 计算子图的点权和 s (sub ones).bit_count() if s % 2: continue # 判断子图是否连通 vis u ^ sub # 技巧把不在子图中的节点都标记为已访问 q sub -sub # 随便选一个在子图中的节点开始 BFS vis | q while q 0: x q -q # 出队 q ^ x to g[x.bit_length() - 1] ~vis # 访问 x 的尚未访问过的邻居 q | to # x 的邻居入队 vis | to if vis u: # 所有节点都已访问子图是连通的 ans 1 return ansJavaclass Solution { public int evenSumSubgraphs(int[] nums, int[][] edges) { int n nums.length; int[] g new int[n]; for (int[] e : edges) { int x e[0]; int y e[1]; g[x] | 1 y; g[y] | 1 x; } int ones 0; for (int i 0; i nums.length; i) { ones | nums[i] i; } // 枚举节点集合 U {0,1,2,...,n-1} 的非空子集 sub int u (1 n) - 1; int ans 0; for (int sub 1; sub u; sub) { // 计算子图的点权和 int sum Integer.bitCount(sub ones); if (sum % 2 ! 0) { continue; } // 判断子图是否连通 int vis u ^ sub; // 技巧把不在子图中的节点都标记为已访问 int q sub -sub; // 随便选一个在子图中的节点开始 BFS vis | q; while (q 0) { int x q -q; // 出队 q ^ x; int to g[Integer.numberOfTrailingZeros(x)] ~vis; // 访问 x 的尚未访问过的邻居 q | to; // x 的邻居入队 vis | to; } if (vis u) { // 所有节点都已访问子图是连通的 ans; } } return ans; } }Cclass Solution { public: int evenSumSubgraphs(vectorint nums, vectorvectorint edges) { int n nums.size(); vectorint g(n); for (auto e : edges) { int x e[0], y e[1]; g[x] | 1 y; g[y] | 1 x; } int ones 0; for (int i 0; i nums.size(); i) { ones | nums[i] i; } // 枚举节点集合 U {0,1,2,...,n-1} 的非空子集 sub int u (1 n) - 1; int ans 0; for (int sub 1; sub u; sub) { // 计算子图的点权和 int sum popcount((uint32_t) sub ones); if (sum % 2) { continue; } // 判断子图是否连通 int vis u ^ sub; // 技巧把不在子图中的节点都标记为已访问 int q sub -sub; // 随便选一个在子图中的节点开始 BFS vis | q; while (q 0) { int x q -q; // 出队 q ^ x; int to g[countr_zero((uint32_t) x)] ~vis; // 访问 x 的尚未访问过的邻居 q | to; // x 的邻居入队 vis | to; } ans vis u; // 所有节点都已访问子图是连通的 } return ans; } };Gofunc evenSumSubgraphs(nums []int, edges [][]int) (ans int) { n : len(nums) g : make([]int, n) for _, e : range edges { x, y : e[0], e[1] g[x] | 1 y g[y] | 1 x } ones : 0 for i, x : range nums { ones | x i } // 枚举节点集合 U {0,1,2,...,n-1} 的非空子集 sub u : 1n - 1 for sub : 1; sub u; sub { // 计算子图的点权和 sum : bits.OnesCount(uint(sub ones)) if sum%2 ! 0 { continue } // 判断子图是否连通 vis : u ^ sub // 技巧把不在子图中的节点都标记为已访问 q : sub -sub // 随便选一个在子图中的节点开始 BFS vis | q for q 0 { x : q -q // 出队 q ^ x to : g[bits.TrailingZeros(uint(x))] ^ vis // 访问 x 的尚未访问过的邻居 q | to // x 的邻居入队 vis | to } if vis u { // 所有节点都已访问子图是连通的 ans } } return }位运算队列逐行拆解ones | x i把nums压缩进一个整数第 $i$ 位代表节点 $i$ 权值为 1sum : bits.OnesCount(uint(sub ones))sub ones取出子集内所有权值为 1 的节点OnesCount统计 1 的个数即为子图点权和Go 标准库math/bits自带与 copypasta/bits.go 中OnesCount系列模板一致q : sub -sublowbit取出sub最低位的 1即任选一个子图内节点作为遍历起点-sub即补码取反加一sub -sub只保留最低位 1x : q -q取出当前队首节点对应的位q ^ x将该节点从队列中删除等价于出队to : g[bits.TrailingZeros(uint(x))] ^ vis取出节点x的全部邻居并用^ vis位清空操作剔除已访问节点剩下的即为本次要入队的新节点q | to; vis | to新节点整体入队并标记访问——这正是一次出队、整批入队的集合化 BFS。复杂度分析时间复杂度$\mathcal{O}(m n2^n)$其中 $n$ 是nums的长度$m$ 是edges的长度。每次BFS至多出队 $n$ 个点需要 $\mathcal{O}(n)$ 的时间而点权和计算被压缩到 $\mathcal{O}(1)$。空间复杂度$\mathcal{O}(n)$邻接表从 $\mathcal{O}(nm)$ 降到 $n$ 个整数。方法一与方法二的核心差异在于前者每次子集枚举要付出 $\mathcal{O}(nm)$ 的图遍历代价后者把邻居表访问集合队列全部二进制化单次遍历代价降到 $\mathcal{O}(n)$点权和判断降为 $\mathcal{O}(1)$。仓库中的对应实现与测试佐证本仓库的 leetcode/biweekly/181/c/c.go 正是方法二位运算 BFS的 Go 落地版与题解 README 中的 Go 代码逐行对应仅将vis | to与q | to的顺序微调先标记访问再入队语义等价。配套的 c_test.go 通过仓库统一测试框架调用func Test_c(t *testing.T) { if err : testutil.RunLeetCodeFuncWithFile(t, evenSumSubgraphs, c.txt, 0); err ! nil { t.Fatal(err) } }其底层实现位于 leetcode/testutil/leetcode.goRunLeetCodeFuncWithFile读取用例文件按函数参数个数 返回值个数tcSize : fNumIn fNumOut对文本行分组逐组构造输入并调用目标函数校验输出。结合 c.txt 中的两组用例[1,0,1] 链状边 → 2[1] 无边 → 0可以完整验证算法的正确性用例 1三个节点中{0,2}点权和为 2偶数且连通{0,1,2}点权和为 2偶数且连通故答案为 2用例 2单个节点权值为 1唯一非空子集{0}点权和为 1奇数答案为 0。从源码结构可以推断这是仓库 LeetCode 题解的通用工作流README.md存放解题思路与多语言代码xxx.go存放实际提交版本xxx.txt存放由测试框架解析的用例数据xxx_test.go调用 leetcode/testutil 完成自动化校验。延伸仓库中的位运算集合操作模板本题的两大技巧二进制表示集合、lowbit 遍历在本仓库模板库中均有系统化沉淀值得进一步研读copypasta/bits.go包含 lowbit 定义lowbit : func(v int) int { return v -v }、OnesCount相关整数序列模板、isSubset/isPow2/hasAdjacentOnes等集合关系判定copypasta/bits.go、copypasta/bits.gocopypasta/search.go枚举子集的通用模板loopSubset、枚举超集loopSuperset以及 Gospers Hack按字典序枚举定长子集用sub -sub取 lowbit 加速位运算copypasta/graph.goDFS 求连通分量Connected Component的图论基础模板对应本题DFS 后vis u的连通性判定原理。若读者想系统训练同类题目原文档给出的三条专题路线不附外部链接仅作方法论指引为回溯题单的「§4.2 子集型回溯」、图论题单的「§1.1 深度优先搜索DFS」、数据结构题单的「七、并查集」。小结「统计和为偶数的连通子图数量」是一道典型的子集型枚举 图连通性判定综合题数据范围 $n \le 13$ 直接指向 $2^n$ 枚举点权和为偶数在 01 权值下等价于异或和为 0进而可被popcount(sub ones)的 $\mathcal{O}(1)$ 技巧取代连通性判定经历了两级演进朴素 DFS$\mathcal{O}(2^n(nm))$→ 位运算 BFS$\mathcal{O}(m n2^n)$其核心是把访问集合邻居表队列三者全部二进制化代码量反而更短、常数更小。掌握这套二进制集合 lowbit 位掩码遍历的组合拳后可无缝迁移到更大 $n$ 的子集型问题配合 Gospers Hack 枚举定长子集、状态压缩 DP 等这正是本仓库 copypasta 系列模板的用武之地。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐力扣双周赛 181 四题全解数位模拟、峰顶判定、子集连通性枚举与二分第 K 小力扣双周赛 181 四题全解数位模拟、峰顶判定、子集连通性枚举与二分第 K 小 本篇技术指南以灵茶山艾府灵神在 codeforces go 仓库中沉淀的科学计算枚举 GCD 并查集力扣双周赛 145 Q4「LCM 图的连通分量」题解与 codeforces-go 仓库实现枚举 GCD 并查集力扣双周赛 145 Q4「LCM 图的连通分量」题解与 codeforces go 仓库实现 本文围绕力扣双周赛 145 的 Q4科学计算codeforces-go 题解剖析力扣双周赛 176 Q2「前缀连通组」哈希表计数解法codeforces go 题解剖析力扣双周赛 176 Q2「前缀连通组」哈希表计数解法 导读 本题是力扣双周赛 176 的第二题Number of Pre科学计算上一篇InfluxDB Studio可视化工具告别命令行轻松管理时间序列数据库下一篇DeepSpeed × HuggingFace 推理示例全指南在 DeepSpeedExamples 中一行命令跑通文本生成、掩码填充、翻译与扩散模型推理创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考