给定一组 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
提示：
1 <= N <= 2000
0 <= dislikes.length <= 10000
dislikes[i].length == 2
1 <= dislikes[i][j] <= N
dislikes[i][0] < dislikes[i][1]
对于 dislikes[i] == dislikes[j] 不存在 i != j
自我解答
将 N 个人分成两组，两组大小不限，不要求相等。互相讨厌的人不能分在一个组。
因此，只需要将 dislikes 中的人安顿好就行了，其他人随便分就行， 所以，我们只需要关注 dislikes 就行.
那么怎么 着手于 dislikes 呢？
假如有两个组，组1、组2。
分了一对后，下一对，也有两种方式，呈二叉树形式展开，只要有一个分支是可行的，就说明结果是可行的。
但是，这样分支展开时间复杂度太高。可以使用贪心策略。
我们可以从dislikes 中其中一个人 出发， 如 a, 把 a 讨厌的人都找出来, 假如是 [b, c], 那么，我们
就可以把 a 分到 组1， b，c 分到 组2， 同样的, 这就决定了，b 和 c 讨厌的人就必须得分到 组1。
因此，在贪心策略下，假如 d 需要分到 组1， 但是 组1 已经有 d 讨厌的人的话，则就说明分不下去了
很明显，这是一个图遍历的过程，dislikes 本身是一个 边集数组，可以转换成 的邻接表形式。
有些难的是在遍历函数设计上，贪心算法中，每个人其实都是被分配了确定的组，如 "d 必须分配到 组1"
只需要确定是否可以成功分组 和遍历下一个就行了。因此函数可设置为：
def ..(n: int, group_id: int) -> bool:
pass
n: 人编号
group_id: 组编号
深度优先
from collections import defaultdict
class Solution:
def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
def dfs(n, group_id):
if n in groups[group_id]:
return True
disgroup_id = 0 if group_id else 1
if n in groups[disgroup_id]:
return False
groups[group_id][n] = 1
for s in dislikes_map[n]:
if not dfs(s, disgroup_id):
return False
return True
if not dislikes:
return True
groups = [{}, {}]
dislikes_map = defaultdict(list)
for dislike in dislikes:
dislikes_map[dislike[0]].append(dislike[1])
dislikes_map[dislike[1]].append(dislike[0])
for n in dislikes_map.keys():
if n in groups[0] or n in groups[1]:
continue
if not dfs(n, 0):
return False
return True
广度优先
增加了队列维护时间，相比 递归的深度优先 效率要低
from collections import defaultdict
class Solution2:
def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:
def bfs(n, group_id):
op_queue = [(n, group_id)]
while op_queue:
n, group_id = op_queue.pop(0)
if n in groups[group_id]:
continue
disgroup_id = 0 if group_id else 1
if n in groups[disgroup_id]:
return False
groups[group_id][n] = 1
for s in dislikes_map[n]:
op_queue.append((s, disgroup_id))
return True
if not dislikes:
return True
groups = [{}, {}]
dislikes_map = defaultdict(list)
for dislike in dislikes:
dislikes_map[dislike[0]].append(dislike[1])
dislikes_map[dislike[1]].append(dislike[0])
for n in dislikes_map.keys():
if n in groups[0] or n in groups[1]:
continue
if not bfs(n, 0):
return False
return True