企业官网建设流程全解析

• 科学计算

本篇文章以 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，要求统计满足以下两个条件的非空子图（即节点的子集及其内部边）数量：

1. 子图中所有节点的权值之和为偶数；
2. 该子图是连通的（任意选两个在子图中的节点，都存在只经过子图内节点的路径）。

关键突破口是数据范围：$n \le 13$。于是可以直接枚举节点集合 $U = {0,1,2,...,n-1}$ 的所有非空子集 $S$，数量只有 $2^n - 1 \le 8191$ 个，完全可以在 $\mathcal{O}(2^n \cdot (n+m))$ 的时间复杂度内穷举完。

对于每个 $S$：

• 若其节点值总和是偶数，且 $S$ 连通，则答案增加一；
• 否则跳过。

如何判断 $S$ 是否连通？随便选一个在 $S$ 中的节点作为 DFS 起点；在 DFS 这张图的过程中，只访问在 $S$ 中的节点；DFS 结束后，如果访问过的节点集合恰好等于 $S$，说明 $S$ 是连通的。这个思路可以进一步利用位运算压成 $\mathcal{O}(1)$ 级别的集合判断（见下文方法二）。

两个关键技巧

代码实现时，文档给出两条核心技巧：

1. 偶数判定的等价变形：由于节点值只有 $0$ 和 $1$，节点值之和是偶数，等价于节点值的异或和为 0（奇数个 1 异或结果为 1，偶数个 1 异或结果为 0），这为后续位运算优化埋下伏笔。
2. 用二进制表示集合：一个整数sub的第 $i$ 位为 1 表示节点 $i$ 属于该集合，集合的交并补、元素判定全部可以落到位运算上（如sub >> i & 1判断 $i$ 是否在sub中）。这一技巧的分类总结可参考仓库模板库 copypasta/bits.go 中关于 lowbit、isSubset、isPow2等集合操作的封装（copypasta/bits.go）。

方法一：朴素 DFS + 二进制枚举（四种语言实现）

原文档为每种语言给出了完整可运行的代码，这里全部保留，并以 Go 版本为主线逐行解读。

Python

class 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 ans

Java

class Solution { private int vis; public int evenSumSubgraphs(int[] nums, int[][] edges) { int n = nums.length; List<Integer>[] 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, List<Integer>[] g) { vis |= 1 << x; // 标记 x 已访问 for (int y : g[x]) { if ((vis >> y & 1) == 0) { // y 没有访问过 dfs(y, g); } } } }

C++

class Solution { public: int evenSumSubgraphs(vector<int>& nums, vector<vector<int>>& edges) { int n = nums.size(); vector<vector<int>> 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; } };

Go

func 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 := 1<<n - 1 for sub := 1; sub <= u; sub++ { // 计算子图的点权异或和 xor := 0 for i, x := range nums { if sub>>i&1 > 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 vis>>y&1 == 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$ 的全集掩码是u，u ^ sub恰好等于u - sub（因为sub ⊆ u），结果是一个"把不在子图中的所有节点都置为已访问"的初始掩码。这样一来 DFS 过程中根本无需显式判断"是否在子图内"——不在子图中的节点天然不可能被再次访问，只需在vis上做并集即可。
• 连通判定：DFS 结束后，若vis == u，说明子图内节点全部可达，子图连通，ans++。

复杂度分析

• 时间复杂度：$\mathcal{O}(2^n(n+m))$，其中 $n$ 是nums的长度，$m$ 是edges的长度。每次 DFS 需要 $\mathcal{O}(n+m)$ 的时间。
• 空间复杂度：$\mathcal{O}(n+m)$。

方法二：位运算 BFS 优化

朴素做法中，每个子集都要用 $\mathcal{O}(n)$ 计算点权和、用 $\mathcal{O}(n+m)$ 做 DFS。原文档给出三步优化，把总复杂度压到 $\mathcal{O}(m + n2^n)$：

1. 压缩点权：既然nums只有 $0$ 和 $1$，可以将其压缩成一个二进制数ones（第 $i$ 位为 1 表示节点 $i$ 的权值为 1），这样可以用 $\mathcal{O}(1)$ 的popcount(sub & ones)计算子集的点权和；
2. 压缩邻接表：用二进制数保存 $g$ 的邻居节点，$g[x]$ 的第 $y$ 位为 1 表示存在边 $(x, y)$；
3. 位运算 BFS：把 DFS 换成"BFS"，用一个二进制数q代替队列，表示"当前在队列中的节点集合"。原文档特别注明：严格来说这不是 BFS，只是遍历图的一种方法——队列中任意节点出队时一次性把全部未访问邻居入队，本质上仍是集合层面的图遍历。

四种语言实现如下：

Python

class 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 ans

Java

class 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; } }

C++

class Solution { public: int evenSumSubgraphs(vector<int>& nums, vector<vector<int>>& edges) { int n = nums.size(); vector<int> 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; } };

Go

func 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 := 1<<n - 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$ 权值为 1；
• sum := bits.OnesCount(uint(sub & ones))：sub & ones取出子集内所有权值为 1 的节点，OnesCount统计 1 的个数即为子图点权和（Go 标准库math/bits自带，与 copypasta/bits.go 中OnesCount系列模板一致）；
• q := sub & -sub：lowbit，取出sub最低位的 1，即任选一个子图内节点作为遍历起点（-sub即补码取反加一，sub & -sub只保留最低位 1）；
• x := 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}(n+m)$ 降到 $n$ 个整数）。

方法一与方法二的核心差异在于：前者每次子集枚举要付出 $\mathcal{O}(n+m)$ 的图遍历代价，后者把"邻居表""访问集合""队列"全部二进制化，单次遍历代价降到 $\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.go：RunLeetCodeFuncWithFile读取用例文件，按函数参数个数 + 返回值个数（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.go）；
• copypasta/search.go：枚举子集的通用模板loopSubset、枚举超集loopSuperset，以及 Gosper's Hack（按字典序枚举定长子集，用sub & -sub取 lowbit 加速位运算）；
• copypasta/graph.go：DFS 求连通分量（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(n+m))$）→ 位运算 BFS（$\mathcal{O}(m + n2^n)$），其核心是把"访问集合""邻居表""队列"三者全部二进制化，代码量反而更短、常数更小。

掌握这套"二进制集合 + lowbit + 位掩码遍历"的组合拳后，可无缝迁移到更大 $n$ 的子集型问题（配合 Gosper's Hack 枚举定长子集、状态压缩 DP 等），这正是本仓库 copypasta 系列模板的用武之地。

• 科学计算