LeetCode 886. Possible Bipartition

Posted on | In |
Words count in article: 359 | Reading time ≈ 2

题目

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:

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

Example 2:

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

Example 3:

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

Note:

  • 1 <= N <= 2000
  • 0 <= dislikes.length <= 10000
  • 1 <= dislikes[i][j] <= N
  • dislikes[i][0] < dislikes[i][1]
  • There does not exist i != j for which dislikes[i] == dislikes[j].

思路

DFS.
Consider the graph on N people formed by the given “dislike” edges. We want to check that each connected component of this graph is bipartite.

For each connected component, we can check whether it is bipartite by just trying to coloring it with two colors. How to do this is as follows: color any node red, then all of it’s neighbors blue, then all of those neighbors red, and so on. If we ever color a red node blue (or a blue node red), then we’ve reached a conflict.

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution(object):
    def possibleBipartition(self, N, dislikes):
        """
        :type N: int
        :type dislikes: List[List[int]]
        :rtype: bool
        """
        graph = collections.defaultdict(list)
        for u, v in dislikes:
            graph[u].append(v)
            graph[v].append(u)
        color = [0] * (N+1)
        for i in range(1, N+1):
            if color[i] != 0:
                continue
            dfs = collections.deque()
            dfs.append(i)
            color[i] = 1
            while dfs:
                cur = dfs.popleft()
                for j in graph[cur]:
                    if color[j] != 0:
                        if color[j] == color[cur]:
                            return False
                    else:
                        color[j] = -color[cur]
                        dfs.append(j)
        return True