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