886. Possible Bipartition

Medium

4.2K

97

We want to split a group of `n`

people (labeled from `1`

to `n`

) into two groups of **any size**. Each person may dislike some other people, and they should not go into the same group.

Given the integer `n`

and the array `dislikes`

where `dislikes[i] = [a`

indicates that the person labeled _{i}, b_{i}]`a`

does not like the person labeled _{i}`b`

, return _{i}`true`

*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:trueExplanation: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:falseExplanation:We need at least 3 groups to divide them. We cannot put them in two groups.

**Constraints:**

`1 <= n <= 2000`

`0 <= dislikes.length <= 10`

^{4}`dislikes[i].length == 2`

`1 <= a`

_{i}< b_{i}<= n- All the pairs of
`dislikes`

are**unique**.

Accepted

179.7K

Submissions

359.2K

Acceptance Rate

50.0%

Seen this question in a real interview before?

1/4

Yes

No

Discussion (0)

Related Topics

Copyright ©️ 2023 LeetCode All rights reserved