Possible Bipartition
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 people who dislike each other should not go into the same group.
Given the integer n and the array dislikes, where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return 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
trueThe first group can be [1, 4], and the second group can be [2, 3].
Example 2
Input
n = 3, dislikes = [[1,2],[1,3],[2,3]]Output
falseWe need at least 3 groups to divide them, so we cannot put everyone into two groups.
Constraints
- 1 <= n <= 2000
- 0 <= dislikes.length <= 10^4
- dislikes[i].length == 2
- 1 <= ai < bi <= n
- All the pairs of
dislikesare unique.