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

这是 LeetCode 3910 的 Python3 实现题目要求统计节点和为偶数的连通诱导子图数量。思路由于 n \le 13可以枚举所有非空子集最多 2^{13}-1 8191 个对每个子集1. 计算节点值之和若为奇数则跳过2. 用 DFS/BFS 检查诱导子图是否连通使用位掩码表示子集高效判断连通性。pythonclass Solution:def evenSumSubgraphs(self, nums: list[int], edges: list[list[int]]) - int:n len(nums)# 建图g [[] for _ in range(n)]for u, v in edges:g[u].append(v)g[v].append(u)m (1 n) - 1 # 全1掩码ans 0# 枚举所有非空子集 sub (1 ~ 2^n - 1)for sub in range(1, m 1):# 1. 计算子集节点值之和s 0tmp subwhile tmp:i (tmp -tmp).bit_length() - 1 # 最低位的1的索引s nums[i]tmp tmp - 1 # 去掉最低位的1# 和为奇数跳过if s 1:continue# 2. 检查诱导子图是否连通# vis: 已访问标记。不在子集中的节点视为已访问vis m ^ sub# 从子集中任意一个节点开始DFSstart (sub -sub).bit_length() - 1 # 最低位的1的索引# DFSstack [start]vis | 1 startwhile stack:u stack.pop()for v in g[u]:if not (vis v) 1: # v未访问vis | 1 vstack.append(v)# 如果所有位都是1说明子集内所有节点连通if vis m:ans 1return ans更简洁的版本使用内置函数pythonclass Solution:def evenSumSubgraphs(self, nums: list[int], edges: list[list[int]]) - int:n len(nums)g [[] for _ in range(n)]for u, v in edges:g[u].append(v)g[v].append(u)m (1 n) - 1ans 0for sub in range(1, m 1):# 计算和s sum(nums[i] for i in range(n) if sub i 1)if s 1:continue# BFS检查连通性start (sub -sub).bit_length() - 1vis m ^ subq [start]vis | 1 startfor u in q:for v in g[u]:if not (vis v) 1:vis | 1 vq.append(v)if vis m:ans 1return ans关键点要点 说明m (1 n) - 1 n位全1掩码sub 枚举 从 1 到 2^n-1s 1 快速判断奇偶vis m ^ sub 不在子集中的节点设为已访问(sub -sub).bit_length() - 1 取最低位1的索引作为起点vis m 所有节点被访问到说明连通复杂度- 时间复杂度O(2^n \times (n m))- 空间复杂度O(n m)