Bipartite CheckBipartite checking

01Why it exists

Reach for it when you see:Split into two groups, mutually conflicting items that cannot share a group, only two slots or layers or teams, adjacent nodes must differ, odd-length cycles, the setup for bipartite matching, the enemy of my enemy is my friend.

02The core idea

A bipartite graph is one whose nodes split into two groups such that every edge crosses between the groups and no edge stays inside one. Put another way: can you colour every node with one of two colours so that no two adjacent nodes share a colour? What makes this easy to decide is that the colours leave you no choice. Colour the start node 0, and its neighbours can only be 1, and their neighbours can only be 0; that one decision at the start forces the colour of the entire connected component. So there is no trial and error and no backtracking: walk the graph once with BFS (or DFS), colour as you go, and check whether any edge has the same colour at both ends. Under BFS a node's colour is simply the parity of its distance from the start, dist % 2.

Correctness rests on one theorem: a graph is bipartite if and only if it contains no odd-length cycle. One direction is immediate. Walk around a cycle and the colours have to alternate 0, 1, 0, 1; if you return to the start after an odd number of steps the colours do not line up, so an odd cycle can never be coloured. The other direction is exactly what the algorithm guarantees: if edge (u, v) turns out to have the same colour at both ends, then depth[u] and depth[v] have the same parity, and climbing the BFS tree from u and from v up to their meeting point w gives two path lengths, depth[u] − depth[w] and depth[v] − depth[w], whose sum is even — add edge (u, v) and you have an odd cycle. A conflict is therefore never a false alarm caused by picking the wrong colour for the start node; no other colouring can rescue it. Conversely, if the walk finishes with no conflict, the colours in hand are themselves a valid split.

Every node is coloured and enters and leaves the queue exactly once, which is O(V). Each edge of an undirected graph appears twice in the adjacency list and is checked once from each side, which is O(E). The outer loop scans every node looking for an uncoloured start, adding another O(V). Total time is O(V + E). You can stop the instant you hit a conflict, so a "no" may come back quickly, but confirming a "yes" always means looking at every edge. Extra space is the colour array plus the queue, O(V) on top of the graph itself. A recursive DFS is O(V) too, but a single long chain pushes the recursion depth to V, which easily blows Python's recursion limit. If edges arrive one at a time and you need an answer after each one, switch to union-find: split every node into "its own side" and "the opposite side", and each added edge costs near-constant time (the sample only does path halving; add union by size and it is a strict O(E·α(V))).

The most common mistake is starting only from node 0: when the graph is disconnected the other components are never checked at all, so the outer loop must start once from every still-uncoloured node (LeetCode 785 says outright that the graph may be disconnected). The 0s and 1s of any connected component can be swapped wholesale, so c components give 2^c valid colourings; if a problem asks for one group to be as large as possible, you decide component by component. A self-loop (u, u) forces a node to share a colour with itself, which immediately makes the graph non-bipartite, and directed edges are read as undirected. Unlike cycle detection, cycles are fine here — only odd ones matter, and an even cycle like a square is perfectly bipartite. Compared with graph colouring in general, two colours can be decided in linear time, but "can this be coloured with three?" is NP-complete with no known polynomial algorithm. Two colours is the unusually tractable special case.

03The algorithm

1. 1Build an undirected adjacency list (treat directed edges as undirected) and a color array set entirely to -1, meaning not coloured yet.
2. 2Scan the nodes in order. If color[s] == -1, then s starts a new connected component: colour it 0 and push it onto the queue.
3. 3Pop u off the queue and look at each neighbour v. If v is uncoloured, colour it 1 − color[u] and enqueue it; if it is already coloured and color[v] == color[u], return "not bipartite" immediately; if the colours differ, move on.
4. 4When the queue empties, go back to step 2 for the next start node. If the whole graph finishes with no conflict it is bipartite, and the nodes coloured 0 and 1 are the two groups.
5. 5To get an odd cycle as evidence, also track parent and depth. From the two ends of the conflicting edge (u, v), climb from the deeper end first until the two paths meet, then join the paths and add the edge.
6. 6When edges arrive one at a time, use union-find over 2n nodes instead: before adding (u, v), a conflict is find(u) == find(v); otherwise union u with v + n and v with u + n.

04Interactive demo

Both examples have six nodes, A through F, and seven edges, with BFS starting at A and neighbours processed in alphabetical order. "Example 1: bipartite" is two quadrilaterals, A–B–C–D and C–E–F–D, so every cycle is even; it ends with blue (colour 0) on A, C and F, and green (colour 1) on B, D and E. "Example 2: odd cycle" swaps D–F for D–E, adding the triangle C–D–E: while processing C the algorithm finds that neighbour E is also colour 0 and stops right there. The yellow lines mark the odd cycle C–B–A–D–E, made of the two colouring paths plus the conflicting edge, which is the thickest line. A yellow outline means the node is still in the queue and a thick outline means it is being processed; solid blue edges were walked during colouring, and the other edges under inspection are dashed. Note that the odd cycle you find is not necessarily the shortest one, but any of them is enough to prove the colouring is impossible.

05Code

The BFS two-colouring is the heart of it, and the outer loop handles disconnected graphs. The union-find version splits each node into "this side" and "the opposite side", which suits edges arriving one at a time with an answer needed after each one; LeetCode 886 can be written this way too. The Python file also shows how to recover an odd cycle at the point of conflict, turning "not bipartite" into visible evidence. The examples use the same two graphs as the interactive demo, with A through F numbered 0 through 5.

from collections import deque


def bipartite_colors(adj):
    """Two-colour with BFS. Returns each node's colour (0 or 1), or None if not bipartite."""
    n = len(adj)
    color = [-1] * n                          # -1 means not coloured yet
    for s in range(n):                        # the graph may be disconnected: start once per component
        if color[s] != -1:
            continue
        color[s] = 0                          # either colour works for a new component's start
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]   # the neighbour is forced to the opposite colour
                    queue.append(v)
                elif color[v] == color[u]:
                    return None               # both ends same colour: the graph has an odd cycle
    return color


def find_odd_cycle(adj):
    """Return an odd cycle (nodes in order) as evidence when not bipartite; None if bipartite."""
    n = len(adj)
    depth, parent = [-1] * n, [-1] * n
    for s in range(n):
        if depth[s] != -1:
            continue
        depth[s] = 0
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for v in adj[u]:
                if depth[v] == -1:
                    depth[v], parent[v] = depth[u] + 1, u
                    queue.append(v)
                elif depth[v] % 2 == depth[u] % 2:  # the colour is the parity of the BFS level
                    a, b = [u], [v]
                    while a[-1] != b[-1]:           # climb from the deeper end until they meet
                        if depth[a[-1]] >= depth[b[-1]]:
                            a.append(parent[a[-1]])
                        else:
                            b.append(parent[b[-1]])
                    return a + b[-2::-1]            # u -> meeting point -> v, closed by edge v-u
    return None


def first_conflict_edge(n, edges):
    """Add edges one at a time: index of the first edge that breaks bipartiteness, else -1."""
    parent = list(range(2 * n))               # x means "x's side", x + n means "the side opposite x"

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]     # path halving
            x = parent[x]
        return x

    for i, (u, v) in enumerate(edges):
        if find(u) == find(v):                # u and v were already forced onto the same side
            return i
        parent[find(u)] = find(v + n)         # u joins the side opposite v
        parent[find(v)] = find(u + n)         # v joins the side opposite u
    return -1


def build(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    return adj


if __name__ == "__main__":
    # The same graphs as the interactive demo: A..F are numbered 0..5
    ok = [(0, 1), (0, 3), (1, 2), (2, 3), (2, 4), (3, 5), (4, 5)]
    odd = [(0, 1), (0, 3), (1, 2), (2, 3), (2, 4), (3, 4), (4, 5)]
    print(bipartite_colors(build(6, ok)))    # [0, 1, 0, 1, 1, 0]
    print(bipartite_colors(build(6, odd)))   # None
    print(["ABCDEF"[x] for x in find_odd_cycle(build(6, odd))])  # ['C', 'B', 'A', 'D', 'E']
    print(first_conflict_edge(6, odd))       # 5: adding D-E turns C-D-E into a triangle

06Practice

• LeetCode 785Is Graph Bipartite? (the graph may be disconnected)Medium
• LeetCode 886Possible Bipartition (build the graph from dislikes; union-find also works)Medium
• LeetCode 1042Flower Planting With No Adjacent (contrast: four colours, degree at most 3, greedy is enough)Medium
• LeetCode 1129Shortest Path with Alternating Colors (split every node into two states)Medium
• LeetCode 2493Divide Nodes Into the Maximum Number of Groups (check bipartiteness first, then the most levels per component)Hard
• LeetCode 2608Shortest Cycle in a Graph (a non-tree edge plus two BFS paths is a cycle)Hard