Possible Bipartition
Explanation & Solution
Description
Given n people labeled from 1 to n and an array dislikes where dislikes[i] = [a, b] indicates that persons a and b dislike each other, return true if it is possible to split everyone into two groups such that no two people in the same group dislike each other. Otherwise, return false.
Examples
Example 1
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: We can split them into two groups: {1, 4} and {2, 3}. No two people in the same group dislike each other.
Example 2
Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Explanation: No matter how we split 3 people into two groups, at least two people who dislike each other end up in the same group.
Example 3
Input: n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
Output: false
Explanation: The dislike relationships form an odd cycle of length 5, making a valid 2-partition impossible.
Constraints
- 1 <= n <= 2000
- 0 <= dislikes.length <= 10^4
- dislikes[i].length == 2
- 1 <= dislikes[i][0] < dislikes[i][1] <= n
- All pairs in dislikes are unique.
Approach
Graphs pattern
1. Model the Problem as a Graph
- Treat each person as a node (labeled 1 to n).
- Each dislike pair [a, b] becomes an undirected edge between nodes a and b.
- Build an adjacency list to represent the graph.
2. Recognize It as a Bipartite Check
- Splitting people into two groups where no two in the same group dislike each other is exactly the definition of a bipartite graph.
- A graph is bipartite if and only if it contains no odd-length cycles.
3. BFS 2-Coloring
- Initialize a color array where
0means unvisited,1means group A, and-1means group B. - For each unvisited node, start a BFS and assign it color
1. - For every neighbor of the current node:
- If unvisited, assign the opposite color and add to the queue.
- If already colored the same color as the current node, we found a conflict — return false.
4. Handle Disconnected Components
- The graph may not be fully connected. The outer loop ensures every connected component is checked independently.
- If all components pass the 2-coloring check, return true.
Key Insight
This problem is a classic graph bipartiteness check in disguise. The "two groups" constraint maps directly to 2-coloring, and BFS provides an efficient O(n + e) solution where e is the number of dislike pairs.
Visualization
Press play to start 2-coloring check