Graph Theory37 sections · 1633 units
Open in Course

LeetCode 785 Is Graph Bipartite? - The Outer Loop

Handling all components

The graph might be disconnected. Running BFS from node 00 only colors one component. Add an outer loop: iterate through all nodes 00 to n1n-1. If color[i] == -1, that node has not been visited yet. Start a BFS from it.

Each BFS handles one connected component. You need all components to be bipartite. If any single BFS finds a conflict, return false. Only if all components pass do you return true.