题目描述
思路解析动画文字版
记住「建图 → BFS 染两色、相邻强制异色、撞同色就 false」,下面逐帧套它。
先把讨厌关系画成图:1 讨厌 2、1 讨厌 3、2 讨厌 4,连成三条边。此刻所有人都灰着、还没分组。
建好邻接表,记下每个人讨厌哪些人:1 讨厌 2、3;2 讨厌 1、4;3 讨厌 1;4 讨厌 2。color 数组全 0,表示还没人分组。
从还没染色的 1 号开始,把它放进组1(第一种颜色),并放进队列。一个连通块从这里开始扩散。
从队首取出 1 号(组1),看它讨厌的人:2、3。这些人都必须和 1 不同组。
顺着 1→2 这条讨厌边看 2 号:它现在是「未分组」。还没分组,得给它定一组。
2 号还没分组。1 讨厌 2,所以把 2 染成和 1 相反的 组2,并入队等待处理。
顺着 1→3 这条讨厌边看 3 号:它现在是「未分组」。还没分组,得给它定一组。
3 号还没分组。1 讨厌 3,所以把 3 染成和 1 相反的 组2,并入队等待处理。
从队首取出 2 号(组2),看它讨厌的人:1、4。这些人都必须和 2 不同组。
顺着 2→1 这条讨厌边看 1 号:它现在是「组1」。已经分过组了,核对一下会不会和 2 撞同组。
1 号已经在 组1,和 2(组2)正好不同组,这对讨厌关系没问题,继续。
顺着 2→4 这条讨厌边看 4 号:它现在是「未分组」。还没分组,得给它定一组。
4 号还没分组。2 讨厌 4,所以把 4 染成和 2 相反的 组1,并入队等待处理。
从队首取出 3 号(组2),看它讨厌的人:1。这些人都必须和 3 不同组。
顺着 3→1 这条讨厌边看 1 号:它现在是「组1」。已经分过组了,核对一下会不会和 3 撞同组。
1 号已经在 组1,和 3(组2)正好不同组,这对讨厌关系没问题,继续。
从队首取出 4 号(组1),看它讨厌的人:2。这些人都必须和 4 不同组。
顺着 4→2 这条讨厌边看 2 号:它现在是「组2」。已经分过组了,核对一下会不会和 4 撞同组。
2 号已经在 组2,和 4(组1)正好不同组,这对讨厌关系没问题,继续。
队列空了,所有人都染过色、全程没碰到任何「讨厌却同组」的冲突。分组成功:组1 {1, 4}、组2 {2, 3},返回 true。回头看,就是建图后 BFS 二染色、相邻强制异色,撞同色才失败。
边界:无边必 true;三角奇环必 false;不连通要逐块染。
两个追问:等价于判二分图(无奇环);也可用扩展域并查集。
参考代码
from typing import Listfrom collections import dequeclass Solution: def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool: g = [[] for _ in range(n + 1)] for a, b in dislikes: g[a].append(b); g[b].append(a) color = [0] * (n + 1) for i in range(1, n + 1): if color[i]: continue color[i] = 1 q = deque([i]) while q: u = q.popleft() for v in g[u]: if color[v] == color[u]: return False if color[v] == 0: color[v] = -color[u] q.append(v) return True复杂度
- 时间：O(n + e)，建图遍历所有讨厌边 e;BFS 每个人入队出队各一次、每条边被两端各看一次,合计 O(n + e),n 是人数、e 是讨厌对数
- 空间：O(n + e)，邻接表存全部边 O(n + e);color 数组、队列各 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么这题等价于判二分图?
追问用并查集能做吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
蛇梯棋
LeetCode 909 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题