Is Graph Bipartite?
Given an undirected graph with n nodes numbered 0 to n - 1 and a list of edges [u, v], can it be coloured with exactly two colours so that no edge joins two same-coloured nodes? The graph may be disconnected, may contain duplicate edges, and may contain a self-loop.
isBipartite(4, [[0, 1], [1, 2], [2, 3], [3, 0]]) -> true // an even cycle isBipartite(3, [[0, 1], [1, 2], [2, 0]]) -> false // an odd cycle
Hints
Hint 1
A graph is bipartite exactly when it has no odd-length cycle. Assign colour 1 to a start node and BFS, giving each neighbour the opposite colour; a neighbour that already has the same colour proves an odd cycle.
Hint 2
The graph may be disconnected, so loop over all n nodes and start a BFS from every uncoloured one. A self-loop fails naturally: the node is its own same-coloured neighbour.