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

这是 LeetCode 3910 的 C 实现题目要求统计节点和为偶数的连通诱导子图数量。思路由于 n \le 13可以枚举所有非空子集最多 2^{13}-1 8191 个对每个子集1. 计算节点值之和若为奇数则跳过2. 用 DFS/BFS 检查诱导子图是否连通使用位掩码表示子集高效判断连通性。cppclass Solution {public:int evenSumSubgraphs(vectorint nums, vectorvectorint edges) {int n nums.size();vectorvectorint g(n);for (auto e : edges) {g[e[0]].push_back(e[1]);g[e[1]].push_back(e[0]);}int 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) {sum nums[i];}}// 和为奇数跳过if (sum 1) {continue;}// 2. 检查诱导子图是否连通// vis: 已访问标记。不在子集中的节点视为已访问int vis m ^ sub;// 从子集中任意一个节点开始DFSint start __builtin_ctz(sub); // 最低位1的索引// DFS (迭代实现)stackint st;st.push(start);vis | 1 start;while (!st.empty()) {int u st.top(); st.pop();for (int v : g[u]) {if (!(vis v 1)) {vis | 1 v;st.push(v);}}}// 如果所有位都是1说明子集内所有节点连通if (vis m) {ans;}}return ans;}};关键点要点 说明m (1 n) - 1 n位全1掩码sub 枚举 从 1 到 2^n-1sum 1 快速判断奇偶vis m ^ sub 异或不在子集中的位设为1视为已访问__builtin_ctz(sub) GCC内置函数取最低位1的索引作为DFS起点vis m 所有位都为1说明子集中所有节点连通复杂度- 时间复杂度O(2^n \times (n m))其中 m 为边数- 空间复杂度O(n m)