Kimi LeetCode 3910. 统计节点和为偶数的连通子图 Python3实现
这是 LeetCode 3910 的 Python3 实现，题目要求统计节点和为偶数的连通诱导子图数量。
思路
由于 n \le 13，可以枚举所有非空子集（最多 2^{13}-1 = 8191 个），对每个子集：
1. 计算节点值之和，若为奇数则跳过
2. 用 DFS/BFS 检查诱导子图是否连通
使用位掩码表示子集，高效判断连通性。
```python
class Solution:
def evenSumSubgraphs(self, nums: list[int], edges: list[list[int]]) -> int:
n = len(nums)
# 建图
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
m = (1 << n) - 1 # 全1掩码
ans = 0
# 枚举所有非空子集 sub (1 ~ 2^n - 1)
for sub in range(1, m + 1):
# 1. 计算子集节点值之和
s = 0
tmp = sub
while tmp:
i = (tmp & -tmp).bit_length() - 1 # 最低位的1的索引
s += nums[i]
tmp &= tmp - 1 # 去掉最低位的1
# 和为奇数，跳过
if s & 1:
continue
# 2. 检查诱导子图是否连通
# vis: 已访问标记。不在子集中的节点视为"已访问"
vis = m ^ sub
# 从子集中任意一个节点开始DFS
start = (sub & -sub).bit_length() - 1 # 最低位的1的索引
# DFS
stack = [start]
vis |= 1 << start
while stack:
u = stack.pop()
for v in g[u]:
if not (vis >> v) & 1: # v未访问
vis |= 1 << v
stack.append(v)
# 如果所有位都是1，说明子集内所有节点连通
if vis == m:
ans += 1
return ans
```
更简洁的版本（使用内置函数）
```python
class Solution:
def evenSumSubgraphs(self, nums: list[int], edges: list[list[int]]) -> int:
n = len(nums)
g = [[] for _ in range(n)]
for u, v in edges:
g[u].append(v)
g[v].append(u)
m = (1 << n) - 1
ans = 0
for sub in range(1, m + 1):
# 计算和
s = sum(nums[i] for i in range(n) if sub >> i & 1)
if s & 1:
continue
# BFS检查连通性
start = (sub & -sub).bit_length() - 1
vis = m ^ sub
q = [start]
vis |= 1 << start
for u in q:
for v in g[u]:
if not (vis >> v) & 1:
vis |= 1 << v
q.append(v)
if vis == m:
ans += 1
return ans
```
关键点
要点 说明
`m = (1 << n) - 1` n位全1掩码
`sub` 枚举 从 1 到 2^n-1
`s & 1` 快速判断奇偶
`vis = m ^ sub` 不在子集中的节点设为已访问
`(sub & -sub).bit_length() - 1` 取最低位1的索引作为起点
`vis == m` 所有节点被访问到，说明连通
复杂度
- 时间复杂度：O(2^n \times (n + m))
- 空间复杂度：O(n + m)