An undirected graph is given as a list of lists graph, where graph[i] lists the neighbours of node
i (if j is in graph[i] then i is in graph[j]). The graph may be disconnected.
Return True if the nodes can be split into two groups so that every edge joins a node of one
group to a node of the other, and False otherwise.
Examples
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: False
Explanation: nodes 0, 1, 2 form a triangle; no two-way split separates all three edges.
Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: True
Explanation: groups {0, 2} and {1, 3}.
Constraints
0 <= len(graph) <= 2 * 10**4, no self-loops, no duplicate edges.- Target
O(V + E)time.
Goals
- Colour a graph with two colours while traversing it
- Handle disconnected graphs by starting a search from every uncoloured node