← Back to problems
UNSW COMP2521 · hard

BFS: Bipartite Check

BFS: Bipartite Check

Given an undirected graph, decide whether it is bipartite (2-colorable so every edge joins different colors).

BFS-color each component: start color 0, neighbors get the opposite; if an edge joins two same-colored ends it's not bipartite. Handle every component.

Input: line 1 V E; then E lines u v (undirected). Output: YES or NO.

Example: 4 4 / 0 1 / 1 2 / 2 3 / 3 0 -> YES.