The problem
Split n people into two groups given a list of pairs who dislike each other (and must be separated). Return whether such a split exists.
Stuck? Reveal hints one at a time
How to approach it
- 1Build an undirected adjacency list from the dislikes pairs (1-indexed people).
- 2Two-color every component with BFS: neighbors get the opposite color.
- 3A conflict (neighbor already has the same color) means the split is impossible.
- 4No conflicts anywhere → return true.
Key insight
Recognizing the reduction is the whole problem: "separate every disliking pair" is exactly the bipartite 2-coloring constraint.
The solution
Watch out for
- People are 1-indexed — size arrays n+1.
- People with no dislikes form isolated nodes; they can join either group and must not crash the loop.