题目重点：把每条朋友边转为异色约束，用二分图染色检查奇环，并处理不连通图、非对称列表与自环。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 朋友视为无向关系，某一侧列出也约束双方；重复关系合并。
- 仅要求组内无朋友边，不要求两组人数相等，也不要求每组互相连通。
- 训练允许空组，输出可行两组或None；若正式只要求布尔结果，保留染色判断即可。
解题路线
- 每条边(u,v)要求 color[u]≠color[v]，颜色只有0/1。沿边给未染色邻居相反颜色；若已经同色，当前约束不可满足。
- 不能仅检查每个人的朋友人数。三个人互相认识，每人只有两条边，却构成奇环，需要三种颜色；任何两组分法都会留下组内朋友。
- 对每个未染色节点重新启动BFS，覆盖不连通分量与孤立点。各分量可整体反转颜色，互不影响可行性，因此无需为了染色把所有人连成一个图。
- 正确性：BFS赋色等于到起点路径长度奇偶。若有同色边，树路径加这条边形成奇环；奇环无法交替两色闭合。若所有边异色，返回分组直接满足每条朋友约束。
- 训练先把非对称adjacency对称化。若关系实际上有向且“陌生”含义不同，需要先定义哪种关系禁止同组；把有向边端点不同色仍是当前冲突约束，不等于检查有向图是否有环。
- 自环要求一个人与自己异色，直接不可行。若要求两组人数相等，二分图可行只完成第一步，还需对各连通分量的两侧大小做选择组合，当前算法不保证平衡。
手动走一遍
朋友链0—1—2可分[0,2]和[1]，0与2没有朋友边。添加2—0形成三角形就不可行。两个独立边与一个孤立点仍可行，孤立点放哪组都不违反边约束。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
"""Undirected friendship constraints, even if only one adjacency lists an edge.
Return two groups or None if impossible; an empty group is permitted.
"""
from collections import deque
def stranger_groups(friends):
n = len(friends)
graph = [set() for _ in range(n)]
for u, neighbors in enumerate(friends):
for v in neighbors:
if not isinstance(v, int) or isinstance(v, bool) or not 0 <= v < n:
raise ValueError("invalid person ID")
graph[u].add(v)
graph[v].add(u)
color = [-1] * n
for start in range(n):
if color[start] != -1:
continue
color[start] = 0
queue = deque([start])
while queue:
u = queue.popleft()
for v in graph[u]:
if color[v] == -1:
color[v] = 1 - color[u]
queue.append(v)
elif color[v] == color[u]:
return None
return [[u for u in range(n) if color[u] == c] for c in (0, 1)]
复杂度
对称建图、BFS O(V+E) 时间，图/颜色/队列 O(V+E) 空间。若只返回布尔值仍需颜色；返回奇环证据可以额外保留父节点和深度。
易错点与追问
容易失分的边界
- 只从节点0开始漏其他分量。
- 自环被去重时错误丢掉。
- 混淆朋友传递闭包和直接朋友关系。
- 默认两组人数必须相等。
继续深挖
- 怎样返回一条不可行奇环？
- 若必须均分人数还需要什么状态？
- 不断新增朋友边怎样在线检查？
- 输入百万节点如何控制邻接内存？
