Leetcode —— 886. 可能的二分法_力扣题目链接: 886: 可能的二分法

给定一组 N 人（编号为 1, 2, …, N）， 我们想把每个人分进任意大小的两组。

每个人都可能不喜欢其他人，那么他们不应该属于同一组。

形式上，如果 dislikes[i] = [a, b]，表示不允许将编号为 a 和 b 的人归入同一组。

当可以用这种方法将所有人分进两组时，返回 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/possible-bipartition
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
————————————————
解题思路：这道题类似于节点染色（假设染为红色和蓝色），对于当前节点，假设其颜色为红色，则其邻居颜色都需要被染色为蓝色；接着遍历其邻居节点，因为该邻居节点被染色为蓝色，则该邻居节点的邻居节点的颜色需要被染色为红色；

对于上述情况的不断递归，如果对某一个节点进行染色时，该节点已经被染色，同时其颜色和要被进行染色的颜色不同，则不能进行有效划分；

class Solution(object):
    def possibleBipartition(self, N, dislikes):
        graph = collections.defaultdict(list)
        for u, v in dislikes:  # 记录不能作为同一组的各种情况
            graph[u].append(v)
            graph[v].append(u)

        color = {}  # 用于保存已经被染色的节点
        def dfs(node, c = 0):  
            if node in color:  # 如果需要被染色的节点已经染色了
                return color[node] == c  # 判断其需要被染色的颜色和其自身颜色是否一样，不一样则不能进行有效划分
            color[node] = c  # 如果该节点没有被进行染色，则对其进行染色
            return all(dfs(nei, c ^ 1) for nei in graph[node])  # 对当前节点的所有邻居节点进行染色，注意使用异或操作改变需要染色的颜色

        return all(dfs(node) for node in range(1, N+1) if node not in color)  # all()的作用是当所有节点都能正常染色时返回True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15