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 的个数由 s 生成的导出子图是连通的子集 s 中所有结点的值之和为偶数。1 n nums.length 13nums[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是否连通节点值总和和是否为偶数[0]是1否[1]是0是[2]是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的邻居掩码中标记yg[y] | 1 x在y的邻居掩码中标记x这样g[i]的二进制第j位为 1 表示i和j之间有一条边。2. 构建节点值的全局掩码遍历nums数组若nums[i] 1则将整数ones的第i位置 1。最终ones的二进制表示直接对应哪些节点的值为 1。全集掩码u (1n) - 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时反复执行从队列中取出一个节点x q -q得到当前处理的节点对应的单一位掩码q ^ x将该节点从队列中移除。获取该节点的索引通过bits.TrailingZeros(x)得到二进制末尾 0 的个数即该位所在的位置idxGo 特有其他语言可用类似指令。得到该节点尚未访问的邻居to g[idx] ^ vis这里^是“位清除”操作等价于g[idx] (~vis)。vis中包含了所有子集外节点以及当前已经访问过的子集内节点因此^ vis就是从邻居掩码中去掉所有已访问节点留下的to就是既在子集内、又未被访问过的邻居。将这些新邻居加入队列并标记为已访问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完整代码如下packagemainimport(fmtmath/bits)funcevenSumSubgraphs(nums[]int,edges[][]int)(ansint){n:len(nums)g:make([]int,n)for_,e:rangeedges{x,y:e[0],e[1]g[x]|1y g[y]|1x}ones:0fori,x:rangenums{ones|xi}// 枚举节点集合 U {0,1,2,...,n-1} 的非空子集 subu:1n-1forsub:1;subu;sub{// 计算子图的点权和sum:bits.OnesCount(uint(subones))ifsum%2!0{continue}// 判断子图是否连通vis:u^sub// 技巧把不在子图中的节点都标记为已访问q:sub-sub// 随便选一个在子图中的节点开始 BFSvis|qforq0{x:q-q// 出队q^x to:g[bits.TrailingZeros(uint(x))]^vis// 访问 x 的尚未访问过的邻居q|to// x 的邻居入队vis|to}ifvisu{// 所有节点都已访问子图是连通的ans}}return}funcmain(){nums:[]int{1,0,1}edges:[][]int{{0,1},{1,2}}result:evenSumSubgraphs(nums,edges)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-defeven_sum_subgraphs(nums,edges):nlen(nums)# 邻接位掩码g[0]*nforx,yinedges:g[x]|1y g[y]|1x# 值为 1 的结点掩码ones0fori,xinenumerate(nums):ifx:ones|1i u(1n)-1ans0# 枚举所有非空子集forsubinrange(1,u1):# 统计子集中值为 1 的结点个数cnt(subones).bit_count()ifcnt%2!0:continue# 连通性检查BFSvisu^sub# 不在子图中的结点视为已访问qsub-sub# 选取子图中最低位的结点作为起点vis|qwhileq:# 取出队列中的一个结点最低位xq-q q^x idxx.bit_length()-1# 获取该结点未访问过的邻居tog[idx]~visu q|to vis|toifvisu:# 所有结点均被访问子图连通ans1returnans# 示例测试if__name____main__:nums[1,0,1]edges[[0,1],[1,2]]print(even_sum_subgraphs(nums,edges))C完整代码如下#includeiostream#includevector#includecstdintintevenSumSubgraphs(std::vectorintnums,std::vectorstd::vectorintedges){intnnums.size();std::vectorintg(n,0);for(autoe:edges){intxe[0],ye[1];g[x]|(1y);g[y]|(1x);}intones0;for(inti0;in;i){if(nums[i])ones|(1i);}intu(1n)-1;intans0;// 枚举所有非空子集for(intsub1;subu;sub){// 统计子集中值为1的结点个数intcnt__builtin_popcount(subones);if(cnt%2!0)continue;// 连通性检查BFSintvisu^sub;// 不在子图中的结点视为已访问intqsub-sub;// 选子图中最低位的结点作为起点vis|q;while(q){intxq-q;// 取出一个结点q^x;intidx__builtin_ctz(x);// 结点编号inttog[idx]~visu;// 未访问过的邻居q|to;vis|to;}if(visu)ans;// 所有结点均被访问子图连通}returnans;}intmain(){std::vectorintnums{1,0,1};std::vectorstd::vectorintedges{{0,1},{1,2}};std::coutevenSumSubgraphs(nums,edges)std::endl;// 输出 2return0;}