[数据结构与算法]LeetCode每日一题——886. 可能的二分法

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 中每一组都 不同

思路

dfs+染色：

我们可以尝试用「染色法」来解决问题：假设第一组中的人是红色，第二组中的人为蓝色。我们依次遍历每一个人，如果当前的人没有被分组，就将其分到第一组（即染为红色），那么这个人不喜欢的人必须分到第二组中（染为蓝色）。然后任何新被分到第二组中的人，其不喜欢的人必须被分到第一组，依此类推。如果在染色的过程中存在冲突，就表示这个任务是不可能完成的，否则说明染色的过程有效（即存在合法的分组方案）。

具体内容见题解注释

题解

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:
        
        # 统计每个人不喜欢的人的集合，这里下标=人员编号-1
        g = [[] for _ in range(n)]
        for x, y in dislikes:
            g[x - 1].append(y - 1)
            g[y - 1].append(x - 1)
        # 染色列表，color[x] = 0 表示未访问节点 x
        color = [0] * n

        # dfs，先赋值颜色，再判断是否自己和不喜欢的人处于同一个颜色
        def dfs(x: int, c: int):
            color[x] = c
            return all(color[y] != c and (color[y] or dfs(y, -c)) for y in g[x])
        # 每一个人都需要遍历一遍
        return all(c or dfs(i, 1) for i, c in enumerate(color))