这是 LeetCode 3910 的 Rust 实现题目要求统计节点和为偶数的连通诱导子图数量。思路由于 n \le 13可以枚举所有非空子集最多 2^{13}-1 8191 个对每个子集1. 计算节点值之和若为奇数则跳过2. 用 DFS/BFS 检查诱导子图是否连通使用位掩码表示子集高效判断连通性。rustimpl Solution {pub fn even_sum_subgraphs(nums: Veci32, edges: VecVeci32) - i32 {let n nums.len();let mut g: VecVecusize 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;// 从子集中任意一个节点开始DFSlet 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-1sum % 2 ! 0 快速排除奇数和子集vis m ^ sub 异或不在子集中的位设为1视为已访问sub.trailing_zeros() 找到最低位1的索引作为DFS起点vis m 所有位都为1说明子集中所有节点连通复杂度- 时间复杂度O(2^n \times (n m))其中 m 为边数- 空间复杂度O(n m)