Connected Components and Bipartiteness

Wrap a search in a loop over every node and each fresh start stamps a new connected component, still in O(n + m) because every edge is looked at twice. The same breadth-first search can seat nodes on alternating sides; on a ring of six it succeeds, one extra edge creates an odd cycle and the colouring breaks, and that is the whole theorem: a graph is bipartite exactly when it has no odd cycle. We finish with the traps (checking only from node 0, self-loops) and how the search can hand you the odd cycle itself.