2026-08-06：统计节点和为偶数的连通子图。用go语言，给定一个包含 n 个结点的无向图，结点编号从 0 到 n-1。每个结点 i 拥有一个数值 nu
🤖 AI总结
主题
使用位运算和BFS高效统计无向图中节点值和为偶数的连通子图数量。
摘要
文章介绍一种使用位运算和BFS统计无向图中节点值和为偶数的连通子图数量的算法，并提供Go、Python和C++实现。
关键信息
- 1 通过位掩码表示邻接矩阵和节点值，枚举所有非空子集。
- 2 利用位运算技巧实现BFS检查子图连通性。
- 3 算法复杂度为O(n·2^n)，适用于n≤13的场景。
2026-08-06：统计节点和为偶数的连通子图。用go语言，给定一个包含 n 个结点的无向图，结点编号从 0 到 n-1。每个结点 i 拥有一个数值 nums[i]，该数值只能是 0 或 1。图的边由二维列表 edges 提供，其中每个元素 [u_i, v_i] 表示结点 u_i 与 v_i 之间存在一条无向边。
对于图中结点的任意一个非空子集 s，可以构造其导出子图（诱导子图）：该子图包含子集 s 中的所有结点，并且只保留那些两个端点都在 s 内的边。
请你统计并返回满足以下全部条件的非空结点子集 s 的个数：
1. 由 s 生成的导出子图是连通的；
2. 子集 s 中所有结点的值之和为偶数。
1 <= n == nums.length <= 13
nums[i] 是 0 或 1。
0 <= edges.length <= n * (n – 1) / 2。
edges[i] = [ui, vi]。
0 <= ui < vi < n。
所有边都是 互不相同 的。
输入： nums = [1,0,1], edges = [[0,1],[1,2]]
输出： 2
解释：
s
是否连通？
节点值总和
和是否为偶数？
1
0
1
[0,1]
1
[0,2]
否，节点 0 和节点 2 不连通。
2
[1,2]
1
[0,1,2]
2
题目来自力扣3910。
详细步骤
1. 图的压缩表示
• 用一个长度为n的整型数组（或切片）g存储每个节点的邻接关系。
• 对于每条边(x, y)，执行：
•g[x] |= 1 << y（在x的邻居掩码中标记y）
•g[y] |= 1 << x（在y的邻居掩码中标记x）
• 这样，g[i]的二进制第j位为 1 表示i和j之间有一条边。
2. 构建节点值的全局掩码
• 遍历nums数组，若nums[i] == 1，则将整数ones的第i位置 1。
• 最终ones的二进制表示直接对应哪些节点的值为 1。
• 全集掩码u = (1<，所有低
n位均为 1。
3. 枚举所有非空子集
• 使用一个整型变量sub从 1 循环到u，它的二进制位就代表了当前选中的节点子集s。
• 第i位为 1 表示节点i在子集中。
4. 对当前子集sub的过滤与判定
4.1 偶数和的快速判断
• 计算sub & ones：得到该子集中所有值为 1 的节点对应的掩码。
• 调用硬件或库支持的popcount（计算二进制中 1 的个数），得到值为 1 的节点数量sum。
• 若sum % 2 != 0，说明该子集节点值总和为奇数，直接跳过，不再检查连通性。
4.2 BFS 判断连通性（完全基于位运算）
• 这是整个算法最巧妙的地方：不构建显式的队列，只用整型变量完成 BFS。
初始化访问状态：
•vis = u ^ sub
解释：u ^ sub等价于“在所有节点中，将子集中的节点置 0，子集外的节点置 1”。
这样做的目的是：把不在子集中的节点预先标记为“已访问”。后续 BFS 只会在子集内部的节点之间扩展，不会跑到子集外部，且这些外部节点一开始就被视为已经访问过，永远不会再被加入队列。最终判断连通性的条件也因此变得非常简单。
•q = sub & -sub
这是经典的“取最低位 1”的操作，得到一个只有子集内编号最小的节点对应的掩码（例如00100表示节点 2）。将它作为 BFS 的起点。
•vis |= q
把起点也标记为已访问。
BFS 循环：
• 当q != 0时，反复执行：
1. 从队列中取出一个节点：x = q & -q，得到当前处理的节点对应的单一位掩码；q ^= x，将该节点从队列中移除。
2. 获取该节点的索引：
通过bits.TrailingZeros(x)得到二进制末尾 0 的个数，即该位所在的位置idx（Go 特有，其他语言可用类似指令）。
3. 得到该节点尚未访问的邻居：to = g[idx] &^ vis
这里&^是“位清除”操作，等价于g[idx] & (~vis)。vis中包含了所有子集外节点以及当前已经访问过的子集内节点，因此&^ vis就是从邻居掩码中去掉所有已访问节点，留下的to就是既在子集内、又未被访问过的邻居。
4. 将这些新邻居加入队列并标记为已访问：q |= to（并入队列）vis |= to（标记已访问）
循环结束后的判定：
• 如果 BFS 结束时vis == u，说明所有节点（包括子集外的所有节点和子集内的所有节点）都被标记为已访问。
• 由于子集外的节点一开始就已经在vis中，所以vis == u的真正含义是：从起点出发，BFS 访问了子集内的每一个节点。这意味着由该子集诱导的子图是连通的。
• 满足该条件时，答案计数器ans加 1。
5. 返回结果
• 循环结束后，ans即为满足条件的子集数量。
复杂度分析
时间复杂度
• 总子集数为2^n - 1，本题n ≤ 13，故最多 8191 个子集。
• 对每个子集：
• 偶数判定：popcount操作在现代 CPU 上通常为 O(1) 指令，或与位数成比例但这里n很小，视为 O(1)。
• 连通性判定：BFS 的 while 循环次数等于子集中节点在 BFS 树上的边数，最坏情况下每个节点都被处理一次，且每个邻居检查都是位运算，因此复杂度为 O(n)。
• 整体时间复杂度为O(2^n · n)（更精确地说是 O(2^n · n/wordsize)，但 n 很小，可简化为 O(n·2^n)）。在n = 13时约为十万次操作，完全可以瞬间完成。
额外空间复杂度
• 使用了邻接掩码数组g（长度n），以及几个整型变量（ones,u,vis,q等）。
• 没有使用与子集数量相关的动态内存，也未递归。因此额外空间复杂度为O(n)（本题n最大 13，近乎 O(1)）。
这种利用位掩码进行子集枚举和 BFS 的方法，在处理n ≤ 20量级的图论组合问题时非常高效和优雅。
Go完整代码如下：
package main
import (
"fmt"
"math/bits"
)
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< 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
}
func main() {
nums := [] int { 1 , 0 , 1 }
edges := [][] int {{ 0 , 1 }, { 1 , 2 }}
result := evenSumSubgraphs(nums, edges)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
def even_sum_subgraphs(nums, edges):
n = len(nums)
# 邻接位掩码
g = [0] * n
for x, y in edges:
g[x] |= 1 << y
g[y] |= 1 << x
# 值为 1 的结点掩码
ones = 0
for i, x in enumerate(nums):
if x:
ones |= 1 << i
u = (1 << n) - 1
ans = 0
# 枚举所有非空子集
for sub in range(1, u + 1):
# 统计子集中值为 1 的结点个数
cnt = (sub & ones).bit_count()
if cnt % 2 != 0:
continue
# 连通性检查：BFS
vis = u ^ sub # 不在子图中的结点视为已访问
q = sub & -sub # 选取子图中最低位的结点作为起点
vis |= q
while q:
# 取出队列中的一个结点（最低位）
x = q & -q
q ^= x
idx = x.bit_length() - 1
# 获取该结点未访问过的邻居
to = g[idx] & ~vis & u
q |= to
vis |= to
if vis == u: # 所有结点均被访问，子图连通
ans += 1
return ans# 示例测试
if __name__ == "__main__":
nums = [1, 0, 1]
edges = [[0, 1], [1, 2]]
print(even_sum_subgraphs(nums, edges))
C++完整代码如下：
int evenSumSubgraphs(std::vector& nums, std::vector int >>& edges) {
int n = nums.size();
std::vector< int > g(n, 0 );
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 < n; ++i) {
if (nums[i]) ones |= ( 1 << i);
}
int u = ( 1 << n) - 1 ;
int ans = 0 ;
// 枚举所有非空子集
for ( int sub = 1 ; sub <= u; ++sub) {
// 统计子集中值为1的结点个数
int cnt = __builtin_popcount(sub & ones);
if (cnt % 2 != 0 ) continue ;
// 连通性检查（BFS）
int vis = u ^ sub; // 不在子图中的结点视为已访问
int q = sub & -sub; // 选子图中最低位的结点作为起点
vis |= q;
while (q) {
int x = q & -q; // 取出一个结点
q ^= x;
int idx = __builtin_ctz(x); // 结点编号
int to = g[idx] & ~vis & u; // 未访问过的邻居
q |= to;
vis |= to;
}
if (vis == u) ans++; // 所有结点均被访问，子图连通
}
return ans;
}
int main() {
std::vector< int > nums = { 1 , 0 , 1 };
std::vector int >> edges = {{ 0 , 1 }, { 1 , 2 }};
std::cout << evenSumSubgraphs(nums, edges) << std::endl; // 输出 2
return 0 ;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
