当前位置：首页 > news >正文

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

news 2026/8/15 23:00:06

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

思路

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

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

```java
import java.util.*;

class Solution {
private List<Integer>[] g;
private int vis;
private int m;

public int evenSumSubgraphs(int[] nums, int[][] edges) {
int n = nums.length;
// 建图
g = new List[n];
Arrays.setAll(g, k -> new ArrayList<>());
for (int[] e : edges) {
g[e[0]].add(e[1]);
g[e[1]].add(e[0]);
}

m = (1 << n) - 1; // 全1掩码，表示所有节点都在"已访问"状态
int ans = 0;

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

// 2. 检查诱导子图是否连通
// vis: 已访问标记。初始时，不在子集中的节点视为"已访问"（m ^ sub）
// 这样DFS只会在子集内的节点中传播
vis = m ^ sub;

// 从子集中任意一个节点开始DFS（取最高位的1）
int start = Integer.numberOfTrailingZeros(sub);
dfs(start);

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

return ans;
}

private void dfs(int u) {
vis |= (1 << u); // 标记u为已访问
for (int v : g[u]) {
// 如果v未被访问（在子集中且未访问）
if (((vis >> v) & 1) == 0) {
dfs(v);
}
}
}
}
```

关键点解释

要点说明
`m = (1 << n) - 1` n位全1掩码
`sub` 枚举从 1 到 2^n-1，每个整数代表一个子集
`sum % 2 != 0` 快速排除奇数和子集
`vis = m ^ sub` 异或：不在子集中的位设为1（视为已访问），子集中的位为0（待访问）
`Integer.numberOfTrailingZeros(sub)` 找到子集中最低位的1的位置，作为DFS起点
`vis == m` DFS结束后所有位都为1，说明子集中所有节点连通

复杂度

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

查看全文

http://www.jsqmd.com/news/1400981/