千问 LeetCode 2493. 将节点分成尽可能多的组 Python3实现

这道题的核心思路是先判断每个连通分量是否是二分图有奇环则无解再对每个连通分量枚举起点做BFS求最大深度最后累加各分量的最大深度。下面给出一个清晰、高效的 Python3 实现包含详细注释from collections import deque, defaultdictclass Solution:def magnificentSets(self, n: int, edges: List[List[int]]) - int:# 1. 建图节点编号从1到n内部转为0到n-1g [[] for _ in range(n)]for u, v in edges:g[u-1].append(v-1)g[v-1].append(u-1)# 2. 并查集找出所有连通分量parent list(range(n))def find(x):while parent[x] ! x:parent[x] parent[parent[x]]x parent[x]return xdef union(x, y):rx, ry find(x), find(y)if rx ! ry:parent[ry] rxfor u, v in edges:union(u-1, v-1)# 将每个节点归入其连通分量comps defaultdict(list)for i in range(n):comps[find(i)].append(i)# 3. BFS函数以start为根返回该连通分量能分出的最大组数若含奇环返回-1def bfs_max_depth(start):depth {start: 1}q deque([start])max_depth 1while q:u q.popleft()for v in g[u]:if v not in depth:depth[v] depth[u] 1max_depth max(max_depth, depth[v])q.append(v)else:# 相邻节点深度差必须为1否则不是二分图if abs(depth[v] - depth[u]) ! 1:return -1return max_depth# 4. 对每个连通分量枚举所有节点作为起点取最大深度total 0for root, nodes in comps.items():best 0for start in nodes:d bfs_max_depth(start)if d -1:return -1best max(best, d)total bestreturn total算法要点说明步骤 说明建图 将节点编号从1-based转为0-based方便数组索引并查集 快速找出所有连通分量每个分量独立处理二分图判定 在BFS过程中若相邻节点深度差不为1说明存在奇环直接返回-1枚举起点 每个连通分量内以不同节点为根BFS得到的深度可能不同取最大值累加结果 各分量的最大深度相加即为全局最大分组数复杂度分析- 时间复杂度O(n × (n m))其中m为边数。最坏情况下每个连通分量都接近全图枚举所有起点做BFS。- 空间复杂度O(n m)用于存储邻接表、并查集和BFS队列。示例验证示例1n6, edges[[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]]输出4与题目一致示例2n3, edges[[1,2],[2,3],[3,1]]输出-1三角形奇环无法分组这个实现直接利用了题目性质代码简洁且易于理解适合面试或竞赛场景。