# # 【LeetCode】886. Possible Bipartition 解题报告（Python）

## # 题目描述：

Given a set of `N` people (numbered `1, 2, ..., N`), we would like to split everyone into two groups of any size.

Each person may dislike some other people, and they should not go into the same group.

Formally, if `dislikes[i] = [a, b]`, it means it is not allowed to put the people numbered `a` and `b` into the same group.

Return `true` if and only if it is possible to split everyone into two groups in this way.

Example 1:

``````Input: N = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: group1 [1,4], group2 [2,3]
``````

Example 2:

``````Input: N = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
``````

Example 3:

``````Input: N = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false
``````

Note:

1. 1 <= N <= 2000
2. 0 <= dislikes.length <= 10000
3. 1 <= dislikes[i][j] <= N
4. dislikes[i][0] < dislikesiopen in new window
5. There does not exist i != j for which dislikes[i] == dislikes[j].

## # 解题方法

``````class Solution(object):
def possibleBipartition(self, N, dislikes):
"""
:type N: int
:type dislikes: List[List[int]]
:rtype: bool
"""
graph = collections.defaultdict(list)
for dislike in dislikes:
graph[dislike[0] - 1].append(dislike[1] - 1)
graph[dislike[1] - 1].append(dislike[0] - 1)
color = [0] * N
for i in range(N):
if color[i] != 0: continue
bfs = collections.deque()
bfs.append(i)
color[i] = 1
while bfs:
cur = bfs.popleft()
for e in graph[cur]:
if color[e] != 0:
if color[cur] == color[e]:
return False
else:
color[e] = -color[cur]
bfs.append(e)
return True
``````