leetcode 886. 可能的二分法

给定一组 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 <= 2000
0 <= dislikes.length <= 104
dislikes[i].length == 2
1 <= dislikes[i][j] <= n
ai < bi
dislikes 中每一组都 不同

思路：用「染色法」来解决，第一组颜色标记为 1， 则相邻组的颜色标记为 2，遍历时，如果发现邻节点已经被染色，且和当前节点的颜色相同，说明是不能划分为两组的。
可采用 dfs 和 bfs 来做

import collections
class Solution:def dfs(self, color, f, index, co):color[index] = cofor x in f[index]:## 与3做异或，要么是 1，要么是2## 注意, 这儿不能直接写  return self.dfs(color, f, x, co^3)if color[x] == 0 and not self.dfs(color, f, x, co^3):return Falseelse:  ## 和 当前进行比较，如果颜色相同, 直接返回 Falseif color[x] == co:return Falsereturn True## 转化成不能有环的问题，染色，两种颜色def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:if len(dislikes) == 0:return Truef = [[] for i in range(n+1)]color = [0]*(n+1)for i in range(0, len(dislikes)):x1, x2 = dislikes[i][0], dislikes[i][1]f[x1].append(x2)f[x2].append(x1)for i in range(1, n+1):if color[i] == 0:## 初始颜色设为 1, 设成 2 也 okif not self.dfs(color, f, i, 1):return Falsereturn True

bfs:

import collections
class Solution:## 转化成不能有环的问题def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:if len(dislikes) == 0:return True### 对已经遍历过&&并已加入 graph 的 index 做标记f = [[] for i in range(n+1)]vis = [0]*(n+1)for i in range(0, len(dislikes)):x1, x2 = dislikes[i][0], dislikes[i][1]f[x1].append(x2)f[x2].append(x1)for i in range(1, n+1):if vis[i] == 0:p = collections.deque()p.append((i, 1))while len(p) > 0:x1, color = p.popleft()vis[x1] = colornewColor = color^3for x in f[x1]:## 如果 x 没有被访问过if vis[x] == 0:p.append((x, newColor))else:  ## 否则和当前的  colr 比较if color == vis[x]:return Falsereturn True