Kimi LeetCode 3910. 统计节点和为偶数的连通子图 Rust实现

这是 LeetCode 3910 的 Rust 实现，题目要求统计节点和为偶数的连通诱导子图数量。

思路

由于 n \le 13，可以枚举所有非空子集（最多 2^{13}-1 = 8191 个），对每个子集：
1. 计算节点值之和，若为奇数则跳过
2. 用 DFS/BFS 检查诱导子图是否连通

使用位掩码表示子集，高效判断连通性。

```rust
impl Solution {
pub fn even_sum_subgraphs(nums: Vec<i32>, edges: Vec<Vec<i32>>) -> i32 {
let n = nums.len();
let mut g: Vec<Vec<usize>> = vec![vec![]; n];
for e in &edges {
let u = e[0] as usize;
let v = e[1] as usize;
g[u].push(v);
g[v].push(u);
}

let m = (1usize << n) - 1; // 全1掩码
let mut ans = 0;

// 枚举所有非空子集 sub (1 ~ 2^n - 1)
for sub in 1..=m {
// 1. 计算子集节点值之和
let mut sum = 0i32;
for i in 0..n {
if (sub >> i) & 1 == 1 {
sum += nums[i];
}
}
// 和为奇数，跳过
if sum % 2 != 0 {
continue;
}

// 2. 检查诱导子图是否连通
// vis: 已访问标记。不在子集中的节点视为"已访问"
let mut vis = m ^ sub;

// 从子集中任意一个节点开始DFS
let start = sub.trailing_zeros() as usize;

// DFS (迭代实现)
let mut stack = vec![start];
vis |= 1 << start;

while let Some(u) = stack.pop() {
for &v in &g[u] {
if (vis >> v) & 1 == 0 {
vis |= 1 << v;
stack.push(v);
}
}
}

// 如果所有位都是1，说明子集内所有节点连通
if vis == m {
ans += 1;
}
}

ans
}
}
```

关键点

要点 说明
`m = (1usize << n) - 1` n位全1掩码
`sub` 枚举 从 1 到 2^n-1
`sum % 2 != 0` 快速排除奇数和子集
`vis = m ^ sub` 异或：不在子集中的位设为1（视为已访问）
`sub.trailing_zeros()` 找到最低位1的索引，作为DFS起点
`vis == m` 所有位都为1，说明子集中所有节点连通

复杂度

- 时间复杂度：O(2^n \times (n + m))，其中 m 为边数
- 空间复杂度：O(n + m)