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] = 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31