Bipartite Graph Check

Can You Split Them Into Two Teams?

Imagine you are a teacher dividing students into two teams for a debate. Some pairs of students are rivals and refuse to be on the same team. Can you always find an assignment that keeps every pair of rivals on opposite teams? And if so, how do you find it efficiently?

This is the graph 2-coloring problem. Model each student as a node and each rivalry as an edge. You need to assign each node one of two colors, say 0 and 1, such that no edge connects two nodes of the same color. A graph that admits such a coloring is called bipartite. Every bipartite graph can be partitioned into two independent sets where all edges go between the sets, never within them.

The BFS Two-Coloring Approach

The standard algorithm for checking bipartiteness uses BFS. Pick any uncolored node, assign it color 0, and place it in a queue. Then process the queue: for each node you dequeue, look at all its neighbors. If a neighbor has not been colored yet, assign it the opposite color (1 if the current node is 0, 0 if the current node is 1) and enqueue it. If a neighbor is already colored and its color matches the current node's color, you have found a conflict. Two adjacent nodes want the same color, which means the graph is not bipartite.

The expression 1 - color[node] is a clean way to flip between 0 and 1. If the current node has color 0, its neighbors get 1 - 0 = 1. If the current node has color 1, its neighbors get 1 - 1 = 0.

Walking Through a Bipartite Graph

Consider a graph with 6 nodes and these edges: 0-1, 0-3, 1-2, 2-3, 3-4, 4-5.

Start BFS from node 0. Color it 0.

Process node 0 (color 0). Neighbors are 1 and 3. Neither is colored. Color both 1. Queue: [1, 3].

Process node 1 (color 1). Neighbor 0 is already color 0, which differs from 1, so no conflict. Neighbor 2 is uncolored. Color it 0. Queue: [3, 2].

Process node 3 (color 1). Neighbor 0 is color 0, fine. Neighbor 2 is color 0, fine. Neighbor 4 is uncolored. Color it 0. Queue: [2, 4].

Process node 2 (color 0). Neighbor 1 is color 1, fine. Neighbor 3 is color 1, fine. Queue: [4].

Process node 4 (color 0). Neighbor 3 is color 1, fine. Neighbor 5 is uncolored. Color it 1. Queue: [5].

Process node 5 (color 1). Neighbor 4 is color 0, fine. Queue is empty.

No conflicts were found. The graph is bipartite with partition {0, 2, 4} in color 0 and {1, 3, 5} in color 1. Every edge crosses between the two groups.

Walking Through a Non-Bipartite Graph

Now consider a triangle: nodes 0, 1, 2 with edges 0-1, 1-2, 0-2.

Start from node 0. Color it 0. Process node 0: color neighbors 1 and 2 as 1. Queue: [1, 2].

Process node 1 (color 1). Neighbor 0 is color 0, fine. Neighbor 2 is color 1, which is the same as node 1's color. Conflict. The graph is not bipartite.

The triangle is an odd cycle of length 3, and no 2-coloring can handle it. If you color 0 as 0, then 1 must be 1, and 2 must be 0 (because it neighbors 1). But 2 also neighbors 0, and both are color 0. There is no escape.

Code: Bipartite Check via BFS

For LeetCode 785, the input graph is an adjacency list where graph[i] is the list of neighbors of node i, and you must determine whether the graph is bipartite.

from collections import deque

def is_bipartite(graph):
    n = len(graph)
    color = [-1] * n

    for start in range(n):
        if color[start] != -1:
            continue
        queue = deque([start])
        color[start] = 0
        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                if color[nei] == -1:
                    color[nei] = 1 - color[node]
                    queue.append(nei)
                elif color[nei] == color[node]:
                    return False
    return True

The color array starts as all -1, meaning uncolored. The outer loop ensures that every connected component is checked, which is critical for disconnected graphs. Within each component, BFS assigns alternating colors and watches for conflicts.

Why Odd Cycles Break Bipartiteness

A graph is bipartite if and only if it contains no odd-length cycle. Here is the intuition.

In a 2-coloring, every edge flips the color. Walking along a path, the color alternates: 0, 1, 0, 1, 0, 1, and so on. After traversing an even number of edges, you return to the original color. After an odd number, you land on the opposite color.

A cycle brings you back to the starting node. If the cycle has even length, you return to the same color you started with, and there is no conflict. If the cycle has odd length, you return needing the opposite color, but the starting node already has its original color. That is a contradiction. No 2-coloring can satisfy all the edges in an odd cycle.

Even cycles are perfectly fine. A cycle of length 4, like 0-1-2-3-0, can be 2-colored as 0, 1, 0, 1. A cycle of length 6 works the same way. It is specifically odd cycles that cause trouble, and a single odd cycle anywhere in the graph is enough to make it non-bipartite.

Handling Disconnected Graphs

The graph might not be connected. If you only BFS from node 0, you will miss any nodes in other connected components. Those components might have their own odd cycles that would make the graph non-bipartite.

The solution is the outer for-loop: iterate through all nodes 0 to n-1, and for each uncolored node, start a new BFS from it. This guarantees every component is examined. A graph is bipartite only if every one of its connected components is bipartite.

Possible Bipartition (LeetCode 886)

This problem gives you n people numbered 1 to n and a list of pairs who dislike each other. You need to determine whether you can split everyone into two groups such that no two people who dislike each other are in the same group.

This is exactly bipartite checking with different framing. Build a graph where each dislike pair is an edge, then check if the graph is bipartite. The people are the nodes, the dislikes are the edges, and the two groups are the two colors.

from collections import deque, defaultdict

def possible_bipartition(n, dislikes):
    graph = defaultdict(list)
    for u, v in dislikes:
        graph[u].append(v)
        graph[v].append(u)

    color = [-1] * (n + 1)  # 1-indexed
    for start in range(1, n + 1):
        if color[start] != -1:
            continue
        queue = deque([start])
        color[start] = 0
        while queue:
            node = queue.popleft()
            for nei in graph[node]:
                if color[nei] == -1:
                    color[nei] = 1 - color[node]
                    queue.append(nei)
                elif color[nei] == color[node]:
                    return False
    return True

The only differences from the basic bipartite check are that the nodes are 1-indexed and the graph is built from the dislike pairs rather than given as an adjacency list. The core BFS logic is identical.

Union-Find Alternative

You can also check bipartiteness using Union-Find (Disjoint Set Union). The idea is based on a key property: in a bipartite graph, every neighbor of node u must be in the opposite group from u. Therefore, all neighbors of u must be in the same group as each other.

For each node u, union all of u's neighbors together. Then check: if u and any of its neighbors end up in the same set, the graph is not bipartite.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]
            x = self.parent[x]
        return x

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1

def is_bipartite_uf(graph):
    n = len(graph)
    uf = UnionFind(n)
    for node in range(n):
        for nei in graph[node]:
            if uf.find(node) == uf.find(nei):
                return False
            uf.union(graph[node][0], nei)
    return True

For each node, we check whether it has already been merged with any of its neighbors (which would mean they ended up on the same side, a contradiction). If not, we union all neighbors together, enforcing that they share one side. This approach avoids explicit coloring and can be useful when Union-Find is already part of your solution for other reasons.

Complexity Analysis

The BFS approach visits every node once and examines every edge once, giving $O(V + E)$ time and $O(V)$ space for the color array and queue.

The Union-Find approach also processes every edge once. With path compression and union by rank, each find and union operation is nearly $O(1)$ amortized (technically $O(\alpha(V))$, where alpha is the inverse Ackermann function). So the total time is $O(V + E \cdot \alpha(V))$, which is effectively $O(V + E)$ in practice. Space is $O(V)$ for the parent and rank arrays.

Both approaches are optimal since you must inspect every edge at least once to determine bipartiteness. The BFS approach is more straightforward and is typically the one you should reach for first. The Union-Find approach is worth knowing as an alternative, especially when the problem involves dynamic edge additions or when you are already using Union-Find for connected component tracking.

Recognizing this pattern

You're probably looking at a bipartite check when:

• The problem asks whether you can two-color a graph or partition nodes into two sets with no intra-set edge
• You need to split people into two teams, two rooms, or two groups so that every "dislikes" or "conflicts with" pair lands on opposite sides
• The graph encodes mutual incompatibilities and you must decide if a valid binary assignment exists
• The structure of the problem boils down to checking for odd-length cycles

Common templates:

• BFS two-coloring: assign one color to the start node, alternate colors level by level, fail if a neighbor has the same color. Example: Is Graph Bipartite?.
• DFS two-coloring: recursively color neighbors with the opposite color while detecting conflicts. Example: Possible Bipartition.
• Union-Find on enemy pairs: union each node with the "enemy of its enemy" and check that no node ends up unioned with a direct enemy. Example: Possible Bipartition.
• Bipartite matching setup: confirm the graph is bipartite before running Hungarian or augmenting-path matching. Example: Maximum Number of Accepted Invitations.