The core fact behind 2-colouring: in a connected graph, BFS from any node gives every node a depth, and colouring by depth % 2 is the only candidate 2-colouring (up to swapping the colours). So the graph is bipartite exactly when no edge joins two nodes of the same parity. Such an edge closes an odd cycle.
The graph is undirected and connected, with nodes 0 .. n-1 and edges a list of pairs (a, b). Implement bad_edges(n, edges) -> list[tuple[int, int]]:
- BFS from node
0to get each node's depth (number of edges on a shortest path from0). - Colour node
vwithdepth[v] % 2. - Return every edge whose two endpoints got the same colour, as the original tuples in their original order. An empty list means the graph is bipartite.
# square 0-1-2-3-0: even cycle
bad_edges(4, [(0, 1), (1, 2), (2, 3), (3, 0)]) # []
# triangle 0-1-2 with a tail 2-3
bad_edges(4, [(0, 1), (1, 2), (2, 0), (2, 3)]) # [(1, 2)] depths: 0->0, 1->1, 2->1, 3->2
Constraints: 1 <= n <= 10^5, n - 1 <= len(edges) <= 2 * 10^5, the graph is connected. A self-loop (v, v) is a bad edge (a cycle of length 1 is odd).
Show hint
use a deque for the BFS so each node gets its shortest depth; then one pass over the edges compares depth[a] % 2 with depth[b] % 2.