188. Check if a Graph Is Bipartite

Given an undirected graph with n vertices and m edges, print 'Yes' if its vertices can be split into two groups such that every edge connects a vertex in one group to a vertex in the other (equivalently, it has no odd-length cycle), otherwise print 'No'.

Input: The first line contains n, the number of vertices. The second line contains m, the number of edges. Each of the next m lines contains two integers, an undirected edge. Output: Print 'Yes' if the graph is bipartite, otherwise print 'No'.

1 <= n <= 10^5

This 2-coloring technique must be run separately for EVERY connected component (a graph can have multiple disconnected pieces, each needing its own independent bipartite check) - forgetting components other than the first is a common oversight.

Check whether a graph's vertices can be split into two groups so every edge connects one group to the other. Brute force: Try every possible way of splitting vertices into two groups directly and check all edges - this is exponential (2^n possible splits), impractical for large graphs. Optimised: A single BFS/DFS-based 2-coloring pass directly constructs a valid bipartition if one exists, or immediately detects a CONFLICT (an edge connecting two same-colored vertices) if none exists - equivalent to checking for any odd-length cycle, but far more direct to implement.

For each vertex not yet visited, start a breadth-first search from it, assigning it one of two colors and then alternating the color assigned to each newly discovered neighbor level by level. Whenever an edge is found connecting two vertices that already have the same color, the graph is immediately declared not bipartite. Repeating this for every connected component (since the graph need not be connected) and finding no such conflicting edge anywhere confirms the graph is bipartite, using only a straightforward linear scan with a queue and a color array. Time: O(n + m) Space: O(n)

Enumerate every possible way of assigning each of the n vertices one of two colors (2^n total colorings), and for each candidate coloring check whether all m edges connect vertices of different colors. If any coloring passes this check for every edge, the graph is bipartite and the answer is 'Yes'; if none does, it's 'No'. This is exhaustive and guaranteed correct, but the number of colorings to check grows exponentially with the number of vertices, making it usable only for very small graphs. Time: O(2^n * m) Space: O(n)

Maintain a disjoint-set structure over 2n elements, where vertex u is represented by both u (its 'own' identity) and u+n (its 'opposite' identity). For every edge (u, v), union u with v+n and also union v with u+n, since an edge forces u and v into opposite groups. After processing all edges, the graph is bipartite exactly when no vertex u ever ends up in the same set as its own opposite u+n; check this for every vertex at the end. Union-Find operations run in near-constant time each thanks to path compression and union by rank, giving a near-linear overall algorithm. Time: O((n + m) * alpha(n)) Space: O(n)

1. Try 2-COLORING the graph with a BFS or DFS: color the starting vertex one color. 2. For every neighbor, assign it the OPPOSITE color of the current vertex. 3. If you ever need to color a vertex DIFFERENTLY from a color it's already been assigned, the graph is NOT bipartite.

Time: O(n + m) - one BFS/DFS pass (per connected component) visiting every vertex and edge once. Space: O(n), for the color-tracking array and the traversal queue/stack.

Test a graph containing an odd-length cycle (expect 'No'), a disconnected graph where each component must be checked independently, and n at the upper bound of 10^5.

Be ready to state the equivalent mathematical characterization explicitly: a graph is bipartite if and only if it contains NO odd-length cycle - useful for quick sanity-checking small examples by eye.