Possible Bipartition
Medium · Graphs · Depth-First Search · Breadth-First Search · Union Find · Graph
Problem
You want to split n people, labeled 1 to n, into two groups of any size. Each dislikes[i] = [a, b] says that person a and person b refuse to be in the same group.
Return true if a split into two groups that respects every dislike exists, and false otherwise.
Examples
Input: n = 4, dislikes = [[1,2],[3,4],[2,3]] Output: true
Put {1, 3} in one group and {2, 4} in the other.
Input: n = 3, dislikes = [[1,2],[2,3],[1,3]] Output: false
Three people who all dislike each other cannot fit in two groups.
Input: n = 2, dislikes = [] Output: true
Nobody has a conflict.
Constraints
- 1 <= n <= 2000
- 0 <= len(dislikes) <= 10^4
- dislikes[i] == [a, b] with 1 <= a < b <= n
- All pairs are distinct
Approaches
- Sweep the pairs until nothing changes — time O(n · e), space O(n)
Follow-up
What if the dislikes arrive one at a time and you must say after each one whether a split still exists? Recoloring the graph each time is slow. A union-find that stores, for each person, whether they are in the same group as their set's root answers each new pair in near-constant time.
Related problems
Start free on Cariara · Coding problems · System design studio
