目录

• [LeetCode解题报告] 886. 可能的二分法
• • 一、 题目
  • • 1. 题目描述
    • 2. 原题链接
  • 二、 解题报告
  • • 1. 思路分析
    • • 方法1-并查集
      • 方法2-DFS染色
    • 2. 复杂度分析
    • 3.代码实现
  • 三、 本题小结

[LeetCode解题报告] 886. 可能的二分法

一、 题目

1. 题目描述

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

Related Topics

• 深度优先搜索
• 广度优先搜索
• 并查集
• 图

• 👍 173
• 👎 0

2. 原题链接

链接: 886. 可能的二分法

二、 解题报告

1. 思路分析

方法1-并查集

1. 由于题目是最多分两组，那么一个人a不喜欢的人一定都在另一组，那么按这个思路用并查集分完所有人的dislike，然后判断他是否和不喜欢的人在一组即可。

方法2-DFS染色

1. a是红色，a不喜欢的人都是蓝色，蓝色不喜欢的人都是红色。
2. 处理每个人不喜欢的人将其染色，递归这个过程，如果发现要处理的人已经有颜色，且颜色冲突，则返回false

2. 复杂度分析

1. 并查集，用近似O(m) 的时间建立并查集，m是dislike长度，O(1)查询，建图O(m)是最坏时间复杂度O(nlog₂n)
2. DFS染色，建图O(m)，因为每个人都染色，只会访问一边，因此递归O(n+m)，递归深度取决于最长关系。

3.代码实现

下面展示一些 内联代码片。
并查集

class Solution:    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool: # g = collections.defaultdict(list) g = [[] for _ in range(n+1)] for u,v in dislikes:     g[u].append(v)     g[v].append(u)  fathers = list(range(n+1)) def find_father(x):     if fathers[x] != x:  fathers[x] = find_father(fathers[x])     return fathers[x]    def union(x,y):     x = find_father(x)     y = find_father(y)     fathers[x] = y     for i in range(1,n+1):     if len(g[i]) == 0:  continue     neighbor1 = g[i][0]   for neighbor2 in g[i]:  union(neighbor1,neighbor2)   if find_father(i) == find_father(neighbor1):  return False return True 

DFS染色

class Solution:    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool: # g = collections.defaultdict(list) g = [[] for _ in range(n+1)] for u,v in dislikes:     g[u].append(v)     g[v].append(u)  colors = {} def dfs(node,color):     c = colors.get(node)     if c:  return c == color     colors[node] = color     return all(dfs(n,color^1) for n in g[node])  return all(dfs(n,0) for n in  range(1, n+1) if n not in colors)

三、 本题小结

1. dfs比较容易想
2. 并查集一般是用来解决分成同一类，这题给出的直接条件是"不可在同一类"，但是由于限制了只能两组，因此这个"不可在同一类"可以认为是:u的所有邻居v都在同一类