LeetCode 题解工作台
可能的二分法
给定一组 n 人（编号为 1, 2, ..., n ）， 我们想把每个人分进 任意 大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。 给定整数 n 和数组 dislikes ，其中 dislikes[i] = [a i , b i ] ，表示不允许将编号为 a i 和 b i 的人归…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图·DFS·traversal
答案摘要
我们用两种颜色对图进行染色，如果可以完成染色，那么就说明可以将所有人分进两组。 具体的染色方法如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·DFS·traversal 题型思路
题目描述
给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。
给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和 bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。
示例 1：
输入：n = 4, dislikes = [[1,2],[1,3],[2,4]] 输出：true 解释：group1 [1,4], group2 [2,3]
示例 2：
输入：n = 3, dislikes = [[1,2],[1,3],[2,3]] 输出：false
示例 3：
输入：n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]] 输出：false
提示：
1 <= n <= 20000 <= dislikes.length <= 104dislikes[i].length == 21 <= dislikes[i][j] <= nai < bidislikes中每一组都 不同
解题思路
方法一：染色法
我们用两种颜色对图进行染色，如果可以完成染色，那么就说明可以将所有人分进两组。
具体的染色方法如下：
- 初始化所有人的颜色为 ，表示还没有染色。
- 遍历所有人，如果当前人没有染色，那么就用颜色 对其进行染色，然后将其所有不喜欢的人用颜色 进行染色。如果染色过程中出现了冲突，那么就说明无法将所有人分进两组，返回
false。 - 如果所有人都染色成功，那么就说明可以将所有人分进两组，返回
true。
时间复杂度 ，其中 , 分别是人数和不喜欢的关系数。
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
def dfs(i, c):
color[i] = c
for j in g[i]:
if color[j] == c:
return False
if color[j] == 0 and not dfs(j, 3 - c):
return False
return True
g = defaultdict(list)
color = [0] * n
for a, b in dislikes:
a, b = a - 1, b - 1
g[a].append(b)
g[b].append(a)
return all(c or dfs(i, 1) for i, c in enumerate(color))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N + E) where N is the number of people and E is the number of dislikes for DFS/BFS, and almost O(E*α(N)) for Union-Find; space is O(N + E) for adjacency lists or O(N) for Union-Find arrays. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Are you able to model dislikes as a graph and identify conflicts quickly?
- question_mark
Can you implement two-color graph coloring efficiently?
- question_mark
Do you understand both DFS and BFS trade-offs in this context?
常见陷阱
外企场景- error
Forgetting to check all disconnected components, which may miss a conflict.
- error
Assigning colors incorrectly leading to false positive bipartitions.
- error
Assuming Union-Find alone without proper separation logic guarantees correctness.
进阶变体
外企场景- arrow_right_alt
Allowing more than two groups and checking k-partition feasibility.
- arrow_right_alt
Input graph may contain cycles or disconnected subgraphs, testing traversal robustness.
- arrow_right_alt
Edge list may be large and require optimized adjacency representation to avoid TLE.