Given n people and a list of dislike pairs, determine whether they can be split into two groups such that no pair of people who dislike each other ends up in the same group. Pattern focus: Bipartite check. Treat the dislikes as an undirected graph and test whether the graph is bipartite.
n = number of people, dislikes = pair list
true if a two-group partition exists
Example 1:
Input:
n = 4 dislikes = [[1,2],[1,3],[2,4]]
Output:
true
Explanation:
A valid split exists, for example {1,4} and {2,3}.
Example 2:
Input:
n = 3 dislikes = [[1,2],[1,3],[2,3]]
Output:
false
Explanation:
The dislikes form a triangle, which is not bipartite.
Example 3:
Input:
n = 4 dislikes = [[1,3],[1,4],[2,3],[2,4],[3,4]]
Output:
false