JZX轻语：简
LeetCode 886 - 可能的二分法
发表于2024年05月21日
这种与关系相关联的题目一般而言可以使用图来建模，本题目的厌恶关系可以使用无向图连接起来，然后使用染色法对节点进行染色：节点和其相邻的节点不能处在同一个颜色中。我们可以使用DFS递归染色：邻接节点的期望颜色和当前节点的颜色相反，如果邻接节点已经染色且和当前节点处在同一个颜色，则无法进行二分，不满足题意。
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
adj_list = [[] for _ in range(n + 1)]
for u, v in dislikes:
adj_list[u].append(v)
adj_list[v].append(u)
group = [-1] * (n + 1)
def dfs(node: int, desired_group: int):
if group[node] != -1:
if group[node] != desired_group:
return False
return True
group[node] = desired_group
for next_ in adj_list[node]:
if not dfs(next_, 1 - desired_group):
return False
return True
for i in range(1, n + 1):
if group[i] == -1:
if not dfs(i, 0):
return False
return True一开始不正确的做法，主要问题出在如果两人之前都没有标记过，则默认将第一个人(设为x)标记在组0内，但后面可能会有这种情况：组0的某个人y会连接同为组0的x，而x分在组1内是可以的：
class Solution:
def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
group = [-1] * (n + 1)
for u, v in dislikes:
if group[u] == group[v] != -1:
return False
if group[u] != -1:
group[v] = 1 - group[u]
elif group[v] != -1:
group[u] = 1 - group[v]
else: # all -1
group[u] = 0
group[v] = 1
return True错误的样例：
[[1,2],[3,4],[5,6],[6,7],[8,9],[7,8]]