Is Graph Bipartite?
Given an undirected graph as an adjacency list, decide whether its nodes can be split into two groups such that every edge connects a node from one group to the other.
- 1 ≤ n ≤ 100
- No self-loops or parallel edges
- The graph may be disconnected
- Two groups with edges only across = 2-colouring
- A conflict appears when a neighbour already has your colour
- Must handle every component
DFS follows one branch to exhaustion before backtracking, which makes it the natural tool for "which cells/nodes belong together", for enumerating complete paths, and for cycle detection via the recursion stack (gray nodes). It needs only the graph plus a visited set and is easily written recursively.
Assign colours 0/1 while traversing. For each uncoloured node, colour it 0 and DFS: every neighbour must receive the opposite colour; if a neighbour already has the same colour as the current node, an odd cycle exists and the graph is not bipartite. Repeat for every component. If no conflict is found the two colour classes are the required groups.
- BFS colouring by level is identical in cost and avoids recursion depth issues. Union-find with "enemy" tracking also works and suits incremental edge insertion.