Bipartite / Bicoloring

"Check bipartite, maximum bipartite matching, König's theorem, Hall's theorem."

Deep Dive Tutorial

A graph is bipartite if its vertices can be split into two groups such that every edge goes between the groups (no edge within a group). Equivalently: the graph has no odd-length cycle. Equivalently: it's 2-colorable (can be 2-colored with no two adjacent vertices sharing a color). Check in O(V+E) with BFS/DFS.

Bipartite Check — 2-Coloring

Check if graph is bipartite using BFS 2-coloring

function isBipartite(graph) {
    const n = graph.length;
    const color = new Array(n).fill(-1); // -1=uncolored, 0=left, 1=right

    for (let start = 0; start < n; start++) {
        if (color[start] !== -1) continue; // already colored
        color[start] = 0;
        const queue = [start];
        while (queue.length) {
            const u = queue.shift();
            for (const v of graph[u]) {
                if (color[v] === -1) {
                    color[v] = 1 - color[u]; // opposite color
                    queue.push(v);
                } else if (color[v] === color[u]) {
                    return false; // same color = odd cycle = not bipartite
                }
            }
        }
    }
    return true;
}

// DFS version:
function isBipartiteDFS(graph) {
    const color = new Array(graph.length).fill(-1);
    const dfs = (u, c) => {
        color[u] = c;
        for (const v of graph[u]) {
            if (color[v] === c) return false;
            if (color[v] === -1 && !dfs(v, 1-c)) return false;
        }
        return true;
    };
    for (let i = 0; i < graph.length; i++)
        if (color[i] === -1 && !dfs(i, 0)) return false;
    return true;
}

Maximum Bipartite Matching (Hungarian / Augmenting Path)

lightbulb

Maximum bipartite matching: Find the maximum set of edges where no vertex appears twice.

Augmenting path algorithm (O(V×E)):
1. For each left vertex, try to match it to an unmatched right vertex
2. If right vertex is already matched, try to re-match its current left partner to another right vertex (augmenting path)
3. If successful, increase matching count

König's theorem: min vertex cover = max matching in bipartite graph.

Hungarian algorithm for maximum bipartite matching

function maxBipartiteMatching(graph, leftSize, rightSize) {
    const matchL = new Array(leftSize).fill(-1);  // matchL[i] = right node matched to left i
    const matchR = new Array(rightSize).fill(-1); // matchR[j] = left node matched to right j

    function dfs(u, visited) {
        for (const v of graph[u]) {
            if (visited[v]) continue;
            visited[v] = true;
            if (matchR[v] === -1 || dfs(matchR[v], visited)) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        return false;
    }

    let matching = 0;
    for (let u = 0; u < leftSize; u++) {
        const visited = new Array(rightSize).fill(false);
        if (dfs(u, visited)) matching++;
    }
    return { matching, matchL, matchR };
}

Worked Problems

Medium

Medium

Find if Path Exists in Graph

Easy

Solve ↗

Maximum Students Taking Exam (Bipartite Matching)

Hard

Solve ↗

brain

Bipartite problem signals:
- "Can we divide into two groups with no conflict within a group?" → bipartite check
- "Two-color problem / enemy-of-enemy-is-friend" → bipartite check
- "Max pairs / assignments between two sets" → bipartite matching
- "Min vertex cover of bipartite graph" = max matching (König's theorem)
- "Max independent set of bipartite graph" = n - max matching

Bipartite check = no odd cycle:
- BFS 2-coloring: O(V+E), works for disconnected graphs
- Union-Find: doesn't directly detect odd cycles (need special handling)

← All Patterns