540. Possible Bipartition
You are organizing n people, labeled 1 through n, into two groups. Some pairs refuse to share a group: the list dislikes contains entries [a, b] meaning person a and person b must be separated.
Groups may be any size (one may even be empty), and every person must land in exactly one group.
Your function receives the integer n and the array dislikes, and returns true if some split into two groups keeps every disliking pair apart, and false if no such split exists.
Example 1:
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Output: true
Explanation: Put persons 1 and 4 in one group and persons 2 and 3 in the other. Every dislike pair (1–2, 1–3, 2–4) is split across the two groups.
Example 2:
Input: n = 3, dislikes = [[1,2],[1,3],[2,3]]
Output: false
Explanation: All three people dislike each other. With only two groups, some pair is forced together — three mutual enemies form an odd cycle, which cannot be 2-colored.
Constraints:
- 1 ≤ n ≤ 2000
- 0 ≤ dislikes.length ≤ 10⁴
- 1 ≤ a < b ≤ n for every pair [a, b]
- All dislike pairs are distinct.
Hints:
Treat people as graph nodes and each dislike as an edge. The question becomes: can you paint every node one of two colors so that no edge connects two same-colored nodes — i.e., is the graph bipartite?
Color any uncolored person, then push the opposite color onto all their enemies with BFS or DFS. A contradiction (an edge whose endpoints demand the same color) means no split exists. Don't forget the graph may be disconnected — restart from every uncolored person.
Union-Find angle: all enemies of one person must end up together in the opposite group, so union them with each other. If a person is ever united with one of their own enemies, the split is impossible.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: n = 4, dislikes = [[1,2],[1,3],[2,4]]
Expected output: true