Is Graph Bipartite?

Problem

You are given an undirected graph as an adjacency list: graph[u] lists the neighbors of node u, for u in 0..n-1. Decide whether the nodes can be split into two groups such that every edge connects a node in one group to a node in the other. The graph may be disconnected and may have isolated nodes; it has no self-loops or repeated edges.

• There are at most a few hundred nodes.
• graph[u] does not contain u, and if v is in graph[u] then u is in graph[v].

Examples

• graph = [[1,2],[0,3],[0,3],[1,2]] → true. Groups {0, 3} and {1, 2}: a 4-cycle.
• graph = [[1,2,4],[0,2],[0,1,4],[4],[0,2,3]] → false. Nodes 0, 1, 2 form a triangle, and three mutually adjacent nodes cannot fit in two groups.
• graph = [[], [2], [1]] → true. Node 0 is isolated and can go in either group.

Hints

1. Pick a node and put it in group A. Where must all of its neighbors go? And their neighbors?
2. Following that rule, when would you be forced to put a node in both groups?
3. Two-color the graph with BFS/DFS: color each newly reached node the opposite of its discoverer; a neighbor that already has the same color means the graph is not bipartite. Restart from every uncolored node.