LeetCode 题解工作台
将节点分成尽可能多的组
给你一个正整数 n ，表示一个 无向 图中的节点数目，节点编号从 1 到 n 。 同时给你一个二维整数数组 edges ，其中 edges[i] = [a i, b i ] 表示节点 a i 和 b i 之间有一条 双向 边。注意给定的图可能是不连通的。 请你将图划分为 m 个组（编号从 1 开始）…
4
题型
5
代码语言
3
相关题
当前训练重点
困难 · 图·DFS·traversal
答案摘要
由于题目给定的图可能是不连通的，所以我们需要对每个连通分量进行处理，找出每个连通分量的最大分组数，累加得到最终结果。 我们可以枚举每一个点作为第一组的节点，然后使用 BFS 遍历整个连通分量，用一个数组 记录每个连通分量的最大分组数。在代码实现上，我们使用连通分量中的最小节点作为该连通分量的根节点。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
给你一个正整数 n ，表示一个 无向 图中的节点数目，节点编号从 1 到 n 。
同时给你一个二维整数数组 edges ，其中 edges[i] = [ai, bi] 表示节点 ai 和 bi 之间有一条 双向 边。注意给定的图可能是不连通的。
请你将图划分为 m 个组（编号从 1 开始），满足以下要求：
- 图中每个节点都只属于一个组。
- 图中每条边连接的两个点
[ai, bi]，如果ai属于编号为x的组，bi属于编号为y的组，那么|y - x| = 1。
请你返回最多可以将节点分为多少个组（也就是最大的 m ）。如果没办法在给定条件下分组，请你返回 -1 。
示例 1：
输入：n = 6, edges = [[1,2],[1,4],[1,5],[2,6],[2,3],[4,6]] 输出：4 解释：如上图所示， - 节点 5 在第一个组。 - 节点 1 在第二个组。 - 节点 2 和节点 4 在第三个组。 - 节点 3 和节点 6 在第四个组。 所有边都满足题目要求。 如果我们创建第五个组，将第三个组或者第四个组中任何一个节点放到第五个组，至少有一条边连接的两个节点所属的组编号不符合题目要求。
示例 2：
输入：n = 3, edges = [[1,2],[2,3],[3,1]] 输出：-1 解释：如果我们将节点 1 放入第一个组，节点 2 放入第二个组，节点 3 放入第三个组，前两条边满足题目要求，但第三条边不满足题目要求。 没有任何符合题目要求的分组方式。
提示：
1 <= n <= 5001 <= edges.length <= 104edges[i].length == 21 <= ai, bi <= nai != bi- 两个点之间至多只有一条边。
解题思路
方法一：BFS + 枚举
由于题目给定的图可能是不连通的，所以我们需要对每个连通分量进行处理，找出每个连通分量的最大分组数，累加得到最终结果。
我们可以枚举每一个点作为第一组的节点，然后使用 BFS 遍历整个连通分量，用一个数组 记录每个连通分量的最大分组数。在代码实现上，我们使用连通分量中的最小节点作为该连通分量的根节点。
在 BFS 的过程中，我们使用一个队列 存储当前遍历到的节点，用一个数组 记录每个节点到起始节点的距离，用一个变量 记录当前连通分量的最大深度，用一个变量 记录当前连通分量的根节点。
在遍历过程中，如果发现某个节点 的 为 ，说明 还没有被遍历到，我们将 的距离设为 ，更新 ，并将 加入队列 中。如果 的距离已经被更新过，我们检查 和 之间的距离是否为 ，如果不是，说明无法满足题目要求，直接返回 。
时间复杂度 ，空间复杂度 。其中 和 分别为节点数和边数。
class Solution:
def magnificentSets(self, n: int, edges: List[List[int]]) -> int:
g = [[] for _ in range(n)]
for a, b in edges:
g[a - 1].append(b - 1)
g[b - 1].append(a - 1)
d = defaultdict(int)
for i in range(n):
q = deque([i])
dist = [0] * n
dist[i] = mx = 1
root = i
while q:
a = q.popleft()
root = min(root, a)
for b in g[a]:
if dist[b] == 0:
dist[b] = dist[a] + 1
mx = max(mx, dist[b])
q.append(b)
elif abs(dist[b] - dist[a]) != 1:
return -1
d[root] = max(d[root], mx)
return sum(d.values())
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * (n + m)) due to DFS/BFS traversals over each component and checking edges. Space complexity is O(n + m) for adjacency lists and level tracking arrays. |
| 空间 | O(n + m) |
面试官常问的追问
外企场景- question_mark
Checks if you detect non-bipartite graphs and return -1 correctly.
- question_mark
Looks for clear DFS/BFS level assignment to calculate group depth.
- question_mark
Wants handling of disconnected components using Union Find or multiple traversals.
常见陷阱
外企场景- error
Assuming the graph is always connected and missing disconnected components.
- error
Failing to check that edges do not connect nodes in the same group.
- error
Incorrectly calculating maximum depth, leading to underestimated group counts.
进阶变体
外企场景- arrow_right_alt
Maximize groups in a weighted undirected graph with additional constraints on edge weights.
- arrow_right_alt
Compute minimum groups needed when edges define forbidden connections between nodes.
- arrow_right_alt
Handle dynamic graphs where edges can be added or removed and recalculate groups efficiently.