hardGraphsPure DSA~30 min
Partition People Into Two Groups Respecting Dislikes
Some pairs of people dislike each other and must not share a group. Decide whether everyone can be split into exactly two groups with no disliking pair together.
Problem
Given n people (1..n) and a list dislikes where dislikes[i] = [a, b] means a and b cannot be in the same group, return true if it is possible to split everyone into two groups, else false.
Input
An integer n and a dislikes list of [a, b] pairs.
Output
A boolean: whether a valid 2-grouping exists.
Constraints
- 1 <= n <= 2000
- 0 <= dislikes.length <= 10^4
- No duplicate or self dislike pairs.
Examples
Example 1
Input
n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output
true
Group {1,4} and {2,3} satisfy all dislikes.
Example 2
Input
n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output
false
A triangle of mutual dislikes cannot be 2-colored.