#886

Possible Bipartition

specialist · 830 · lc medium +31 · verified · 52.4% accepted · 4,904 likes · top 42%

Description

You want to divide n people (labeled 1 through n) into two groups of any size. Some pairs of people dislike each other and must not be placed in the same group.

Given n and an array dislikes where dislikes[i] = [ai, bi] means persons ai and bi dislike each other, return true if such a partition is possible, or false otherwise.

Example 1:

Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]

Output: true

Explanation: The first group has [1,4], and the second group has [2,3].

Example 2:

Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]

Output: false

Explanation: We need at least 3 groups to divide them. We cannot put them in two groups.

Code

1

2

3

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:

class Solution:
    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool: