Bipartite Graph Check in Coding Interviews: BFS Coloring Explained

by linkjobai

HTML

<!DOCTYPE html>
<html><head><meta charset="utf-8"><title>Bipartite Graph Check in Coding Interviews: BFS Coloring Explained</title></head>
<body>
<h1>Bipartite Graph Check in Coding Interviews: BFS Coloring Explained</h1>
<p>"Is this graph bipartite?" shows up in interviews in many disguises: splitting people into two teams where no two rivals share a team, scheduling exams into two time slots, or checking whether a set of dislike pairs can be satisfied (LeetCode 785 and 886). The core idea is always the same: try to paint every node with one of two colors so that no edge connects two nodes of the same color.</p>
<h2>The idea</h2>
<p>A graph is bipartite exactly when it has no odd-length cycle. You do not need to search for cycles directly. Instead, color greedily: pick an uncolored node, give it color 0, and give every neighbor the opposite color. If you ever find an edge whose two ends already have the same color, the graph is not bipartite.</p>
<h2>BFS solution (Python)</h2>
<pre><code>from collections import deque

def is_bipartite(graph):
    n = len(graph)
    color = [-1] * n
    for start in range(n):          # graph may be disconnected
        if color[start] != -1:
            continue
        color[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]
                    q.append(v)
                elif color[v] == color[u]:
                    return False
    return True
</code></pre>
<p>Time is O(V + E) and space is O(V). DFS works just as well; BFS avoids recursion depth limits on large inputs.</p>
<h2>Common mistakes interviewers watch for</h2>
<ul>
<li>Forgetting the outer loop, so only the first connected component is checked.</li>
<li>Building the adjacency list one-directionally when the input gives undirected pairs (for "possible bipartition", add both u to v and v to...