2026-08-06統(tǒng)計(jì)節(jié)點(diǎn)和為偶數(shù)的連通子圖。用go語言給定一個(gè)包含 n 個(gè)結(jié)點(diǎn)的無向圖結(jié)點(diǎn)編號(hào)從 0 到 n-1。每個(gè)結(jié)點(diǎn) i 擁有一個(gè)數(shù)值 nums[i]該數(shù)值只能是 0 或 1。圖的邊由二維列表 edges 提供其中每個(gè)元素 [u_i, v_i] 表示結(jié)點(diǎn) u_i 與 v_i 之間存在一條無向邊。對(duì)于圖中結(jié)點(diǎn)的任意一個(gè)非空子集 s可以構(gòu)造其導(dǎo)出子圖誘導(dǎo)子圖該子圖包含子集 s 中的所有結(jié)點(diǎn)并且只保留那些兩個(gè)端點(diǎn)都在 s 內(nèi)的邊。請(qǐng)你統(tǒng)計(jì)并返回滿足以下全部條件的非空結(jié)點(diǎn)子集 s 的個(gè)數(shù)由 s 生成的導(dǎo)出子圖是連通的子集 s 中所有結(jié)點(diǎn)的值之和為偶數(shù)。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是否連通節(jié)點(diǎn)值總和和是否為偶數(shù)[0]是1否[1]是0是[2]是1否[0,1]是1否[0,2]否節(jié)點(diǎn) 0 和節(jié)點(diǎn) 2 不連通。2否[1,2]是1否[0,1,2]是2是題目來自力扣3910。詳細(xì)步驟1. 圖的壓縮表示用一個(gè)長度為n的整型數(shù)組或切片g存儲(chǔ)每個(gè)節(jié)點(diǎn)的鄰接關(guān)系。對(duì)于每條邊(x, y)執(zhí)行g(shù)[x] | 1 y在x的鄰居掩碼中標(biāo)記yg[y] | 1 x在y的鄰居掩碼中標(biāo)記x這樣g[i]的二進(jìn)制第j位為 1 表示i和j之間有一條邊。2. 構(gòu)建節(jié)點(diǎn)值的全局掩碼遍歷nums數(shù)組若nums[i] 1則將整數(shù)ones的第i位置 1。最終ones的二進(jìn)制表示直接對(duì)應(yīng)哪些節(jié)點(diǎn)的值為 1。全集掩碼u (1n) - 1所有低n位均為 1。3. 枚舉所有非空子集使用一個(gè)整型變量sub從 1 循環(huán)到u它的二進(jìn)制位就代表了當(dāng)前選中的節(jié)點(diǎn)子集s。第i位為 1 表示節(jié)點(diǎn)i在子集中。4. 對(duì)當(dāng)前子集sub的過濾與判定4.1 偶數(shù)和的快速判斷計(jì)算sub ones得到該子集中所有值為 1 的節(jié)點(diǎn)對(duì)應(yīng)的掩碼。調(diào)用硬件或庫支持的popcount計(jì)算二進(jìn)制中 1 的個(gè)數(shù)得到值為 1 的節(jié)點(diǎn)數(shù)量sum。若sum % 2 ! 0說明該子集節(jié)點(diǎn)值總和為奇數(shù)直接跳過不再檢查連通性。4.2 BFS 判斷連通性完全基于位運(yùn)算這是整個(gè)算法最巧妙的地方不構(gòu)建顯式的隊(duì)列只用整型變量完成 BFS。初始化訪問狀態(tài)vis u ^ sub解釋u ^ sub等價(jià)于“在所有節(jié)點(diǎn)中將子集中的節(jié)點(diǎn)置 0子集外的節(jié)點(diǎn)置 1”。這樣做的目的是把不在子集中的節(jié)點(diǎn)預(yù)先標(biāo)記為“已訪問”。后續(xù) BFS 只會(huì)在子集內(nèi)部的節(jié)點(diǎn)之間擴(kuò)展不會(huì)跑到子集外部且這些外部節(jié)點(diǎn)一開始就被視為已經(jīng)訪問過永遠(yuǎn)不會(huì)再被加入隊(duì)列。最終判斷連通性的條件也因此變得非常簡單。q sub -sub這是經(jīng)典的“取最低位 1”的操作得到一個(gè)只有子集內(nèi)編號(hào)最小的節(jié)點(diǎn)對(duì)應(yīng)的掩碼例如00100表示節(jié)點(diǎn) 2。將它作為 BFS 的起點(diǎn)。vis | q把起點(diǎn)也標(biāo)記為已訪問。BFS 循環(huán)當(dāng)q ! 0時(shí)反復(fù)執(zhí)行從隊(duì)列中取出一個(gè)節(jié)點(diǎn)x q -q得到當(dāng)前處理的節(jié)點(diǎn)對(duì)應(yīng)的單一位掩碼q ^ x將該節(jié)點(diǎn)從隊(duì)列中移除。獲取該節(jié)點(diǎn)的索引通過bits.TrailingZeros(x)得到二進(jìn)制末尾 0 的個(gè)數(shù)即該位所在的位置idxGo 特有其他語言可用類似指令。得到該節(jié)點(diǎn)尚未訪問的鄰居to g[idx] ^ vis這里^是“位清除”操作等價(jià)于g[idx] (~vis)。vis中包含了所有子集外節(jié)點(diǎn)以及當(dāng)前已經(jīng)訪問過的子集內(nèi)節(jié)點(diǎn)因此^ vis就是從鄰居掩碼中去掉所有已訪問節(jié)點(diǎn)留下的to就是既在子集內(nèi)、又未被訪問過的鄰居。將這些新鄰居加入隊(duì)列并標(biāo)記為已訪問q | to并入隊(duì)列vis | to標(biāo)記已訪問循環(huán)結(jié)束后的判定如果 BFS 結(jié)束時(shí)vis u說明所有節(jié)點(diǎn)包括子集外的所有節(jié)點(diǎn)和子集內(nèi)的所有節(jié)點(diǎn)都被標(biāo)記為已訪問。由于子集外的節(jié)點(diǎn)一開始就已經(jīng)在vis中所以vis u的真正含義是從起點(diǎn)出發(fā)BFS 訪問了子集內(nèi)的每一個(gè)節(jié)點(diǎn)。這意味著由該子集誘導(dǎo)的子圖是連通的。滿足該條件時(shí)答案計(jì)數(shù)器ans加 1。5. 返回結(jié)果循環(huán)結(jié)束后ans即為滿足條件的子集數(shù)量。復(fù)雜度分析時(shí)間復(fù)雜度總子集數(shù)為2^n - 1本題n ≤ 13故最多 8191 個(gè)子集。對(duì)每個(gè)子集偶數(shù)判定popcount操作在現(xiàn)代 CPU 上通常為 O(1) 指令或與位數(shù)成比例但這里n很小視為 O(1)。連通性判定BFS 的 while 循環(huán)次數(shù)等于子集中節(jié)點(diǎn)在 BFS 樹上的邊數(shù)最壞情況下每個(gè)節(jié)點(diǎn)都被處理一次且每個(gè)鄰居檢查都是位運(yùn)算因此復(fù)雜度為 O(n)。整體時(shí)間復(fù)雜度為O(2^n · n)更精確地說是 O(2^n · n/wordsize)但 n 很小可簡化為 O(n·2^n)。在n 13時(shí)約為十萬次操作完全可以瞬間完成。額外空間復(fù)雜度使用了鄰接掩碼數(shù)組g長度n以及幾個(gè)整型變量ones,u,vis,q等。沒有使用與子集數(shù)量相關(guān)的動(dòng)態(tài)內(nèi)存也未遞歸。因此額外空間復(fù)雜度為O(n)本題n最大 13近乎 O(1)。這種利用位掩碼進(jìn)行子集枚舉和 BFS 的方法在處理n ≤ 20量級(jí)的圖論組合問題時(shí)非常高效和優(yōu)雅。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}// 枚舉節(jié)點(diǎn)集合 U {0,1,2,...,n-1} 的非空子集 subu:1n-1forsub:1;subu;sub{// 計(jì)算子圖的點(diǎn)權(quán)和sum:bits.OnesCount(uint(subones))ifsum%2!0{continue}// 判斷子圖是否連通vis:u^sub// 技巧把不在子圖中的節(jié)點(diǎn)都標(biāo)記為已訪問q:sub-sub// 隨便選一個(gè)在子圖中的節(jié)點(diǎn)開始 BFSvis|qforq0{x:q-q// 出隊(duì)q^x to:g[bits.TrailingZeros(uint(x))]^vis// 訪問 x 的尚未訪問過的鄰居q|to// x 的鄰居入隊(duì)vis|to}ifvisu{// 所有節(jié)點(diǎn)都已訪問子圖是連通的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 的結(jié)點(diǎn)掩碼ones0fori,xinenumerate(nums):ifx:ones|1i u(1n)-1ans0# 枚舉所有非空子集forsubinrange(1,u1):# 統(tǒng)計(jì)子集中值為 1 的結(jié)點(diǎn)個(gè)數(shù)cnt(subones).bit_count()ifcnt%2!0:continue# 連通性檢查BFSvisu^sub# 不在子圖中的結(jié)點(diǎn)視為已訪問qsub-sub# 選取子圖中最低位的結(jié)點(diǎn)作為起點(diǎn)vis|qwhileq:# 取出隊(duì)列中的一個(gè)結(jié)點(diǎn)最低位xq-q q^x idxx.bit_length()-1# 獲取該結(jié)點(diǎn)未訪問過的鄰居tog[idx]~visu q|to vis|toifvisu:# 所有結(jié)點(diǎn)均被訪問子圖連通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){// 統(tǒng)計(jì)子集中值為1的結(jié)點(diǎn)個(gè)數(shù)intcnt__builtin_popcount(subones);if(cnt%2!0)continue;// 連通性檢查BFSintvisu^sub;// 不在子圖中的結(jié)點(diǎn)視為已訪問intqsub-sub;// 選子圖中最低位的結(jié)點(diǎn)作為起點(diǎn)vis|q;while(q){intxq-q;// 取出一個(gè)結(jié)點(diǎn)q^x;intidx__builtin_ctz(x);// 結(jié)點(diǎn)編號(hào)inttog[idx]~visu;// 未訪問過的鄰居q|to;vis|to;}if(visu)ans;// 所有結(jié)點(diǎn)均被訪問子圖連通}returnans;}intmain(){std::vectorintnums{1,0,1};std::vectorstd::vectorintedges{{0,1},{1,2}};std::coutevenSumSubgraphs(nums,edges)std::endl;// 輸出 2return0;}