这是 LeetCode 3910 的 Java 实现题目要求统计节点和为偶数的连通诱导子图数量。思路由于 n \le 13可以枚举所有非空子集最多 2^{13}-1 8191 个对每个子集1. 计算节点值之和若为奇数则跳过2. 用 DFS/BFS 检查诱导子图是否连通使用位掩码表示子集高效判断连通性。javaimport java.util.*;class Solution {private ListInteger[] 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取最高位的1int 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)
