leetcode886.可能的二分法

给定一组 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] = co for 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 False else: ## 和 当前进行比较，如果颜色相同, 直接返回 False if color[x] == co: return False return True ## 转化成不能有环的问题，染色，两种颜色 def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool: if len(dislikes) == 0: return True f = [[] 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 也 ok if not self.dfs(color, f, i, 1): return False return 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] = color newColor = color^3 for x in f[x1]: ## 如果 x 没有被访问过 if vis[x] == 0: p.append((x, newColor)) else: ## 否则和当前的 colr 比较 if color == vis[x]: return False return True