Pattern #53

Bipartite Graph

Important interview questions, thinking patterns, 2-Coloring Array (-1, 0, 1), Odd Cycle Theorem, Bipartite Matching concepts, and Go templates.

Must Solve

10 core questions — solve these first.

1.Is Graph Bipartite?
BFS/DFS 2-Coloring array (-1=uncolored, 0=group0, 1=group1); nextColor = 1 - currColormedium
2.Possible Bipartition
Build Dislike Graph; 2-Color graph to split people into 2 teams with no enemies on same teammedium
3.Divide Nodes Into the Maximum Number of Groups
Verify Bipartite 2-coloring + BFS diameter per componenthard
4.Two-Color an Undirected Graph
Standard 2-coloring via BFS/DFS checking same-color neighbor conflictsmedium
5.Detect Odd Cycle in Graph
Coloring conflict on same-color edge implies existence of an odd-length cyclemedium
6.Bipartite Graph Using BFS
Queue-based 2-coloring level by level assigning opposite colors to uncolored neighborsmedium
7.Bipartite Graph Using DFS
Recursive 2-coloring passing (1 - currentColor) to neighborsmedium
8.Check Bipartite Graph with Disconnected Components
Outer loop over all 0..n-1 nodes; 2-color each unvisited componentmedium
9.Maximum Bipartite Matching — Concept
Bipartite Graph matching Left Set (Workers) to Right Set (Jobs) with augmenting pathsmedium
10.Matching Applicants to Jobs — Concept
Construct bipartite entity graph + maximum matching assignmentmedium

Also Important

6 more questions worth practicing.

11.Maximum Students Taking Exam
Grid Bipartite Graph / Bitmask DP eliminating adjacent seatshard
12.Matching Workers to Tasks
Bipartite Matching / Priority Queue assignment with pills/requirementshard
13.Assign Resources to Requests
Resource-Request bipartite graph matchingmedium
14.Minimum Vertex Cover in Bipartite Graph — Advanced
Konig's Theorem: Min Vertex Cover size == Max Bipartite Matching sizehard
15.Hopcroft-Karp — Advanced
Fast O(E * sqrt(V)) Maximum Bipartite Matching algorithm using BFS+DFS layershard
16.Hungarian Algorithm — Related Matching Topic
Weighted Maximum Bipartite Matching / Assignment problem in O(V^3)hard

How to Think

Need divide nodes into 2 groups?Bipartite Graph
Every connected node must be opposite?2-Coloring (nextColor = 1 - currColor)
Need check bipartite status?BFS / DFS + Color array (-1, 0, 1)
Does an odd cycle exist?Same-color conflict during 2-coloring

Go Bipartite Graph Templates

BFS 2-Coloring & DFS 2-Coloring in Go

// 1. Bipartite BFS 2-Coloring: O(V + E) Time
func isBipartiteBFS(graph [][]int) bool {
    n := len(graph)
    color := make([]int, n)
    for i := range color { color[i] = -1 } // -1 = uncolored

    for start := 0; start < n; start++ {
        if color[start] != -1 { continue } // Outer loop for disconnected graphs!

        color[start] = 0
        queue := []int{start}

        for len(queue) > 0 {
            node := queue[0]
            queue = queue[1:]

            for _, next := range graph[node] {
                if color[next] == -1 {
                    color[next] = 1 - color[node] // Assign opposite color!
                    queue = append(queue, next)
                } else if color[next] == color[node] {
                    return false // Same-color conflict -> Not Bipartite!
                }
            }
        }
    }
    return true
}

// 2. Bipartite DFS 2-Coloring: O(V + E) Time
func isBipartiteDFS(graph [][]int) bool {
    n := len(graph)
    color := make([]int, n)
    for i := range color { color[i] = -1 }

    var dfs func(u, c int) bool
    dfs = func(u, c int) bool {
        color[u] = c
        for _, v := range graph[u] {
            if color[v] == -1 {
                if !dfs(v, 1-c) { return false }
            } else if color[v] == color[u] {
                return false // Same-color conflict!
            }
        }
        return true
    }

    for i := 0; i < n; i++ {
        if color[i] == -1 && !dfs(i, 0) {
            return false
        }
    }
    return true
}

👉 Total Time: O(V + E) | Space: O(V) color array + stack/queue

The 2-Coloring Array Rule

1. Array Representation: Represent groups using -1 = uncolored, 0 = Group 0, 1 = Group 1.

2. Opposite Color Math: The opposite color of c is calculated with 1 - c.

3. Conflict Rule: If neighbor next is uncolored, assign 1 - color[node] and continue traversal. If color[next] == color[node], a same-color conflict occurs and the graph is NOT bipartite!

The Odd Cycle Theorem & Bipartite Matching

1. Odd Cycle Theorem: A graph is bipartite IF AND ONLY IF it contains NO odd-length cycles! Even-length cycles (e.g. 4-cycle) color cleanly into 2 groups. Odd-length cycles (e.g. 3-node triangle) force a same-color conflict.

2. Trees are Always Bipartite: Trees have zero cycles, so they never contain odd cycles! Any tree can be 2-colored by depth parity (depth % 2).

3. Maximum Bipartite Matching: Problems assigning Workers to Jobs, Drivers to Rides, or Students to Courses naturally form bipartite graphs where edges cross from Left Set to Right Set.

Visual Memory Rule

Bipartite Graph    → Divide nodes into 2 groups with all edges crossing groups
2-Coloring Array   → -1 = uncolored, 0 = Group 0, 1 = Group 1
Opposite Color     → 1 - currentColor
Conflict Check     → color[next] == color[node] -> NOT Bipartite!
Odd-Length Cycle   → Triangle/5-cycle forces same-color edge conflict
Every Tree         → ALWAYS Bipartite (0 odd cycles)

💡 Golden Rule: "Give every neighbor the opposite color. If an edge ever connects two nodes with the same color, the graph is not bipartite."

Common Interview Mistakes

1. Using Boolean Visited Array

A simple boolean visited array tells you if a node was seen, but NOT its color! Use a 3-state color array (-1, 0, 1).

2. Overwriting Assigned Colors

If a neighbor is already colored (color[next] != -1), do NOT overwrite its color! Compare it to current node.

3. Starting From Node 0 Only

The graph may be disconnected! Run an outer loop over all 0..n-1 nodes so every component gets 2-colored.

4. Thinking Any Cycle Breaks Bipartite Status

Even-length cycles (4-cycle, 6-cycle) color cleanly and ARE bipartite! Only ODD-length cycles break bipartite status.

Interview Rules

1. Divide into two teams / groups? → Bipartite Graph 2-Coloring
2. Array colors? → Use -1 = uncolored, 0 = Group 0, 1 = Group 1
3. Opposite color formula? → nextColor = 1 - currentColor
4. Conflict detection? → color[next] == color[node] implies same-color conflict $\implies$ Not Bipartite
5. Disconnected graph? → Outer loop over all 0..n-1 nodes
6. Odd cycle presence? → Graph is NOT Bipartite
7. Entity matching (Workers vs Jobs)? → Bipartite Matching
8. Overall Complexity → Time: O(V + E) | Space: O(V)

Small Rules

Rule 1: Bipartite means splitting graph nodes into 2 groups with all edges crossing.
Rule 2: Uncolored neighbors must be assigned the opposite color (1 - current).
Rule 3: Connecting two same-color nodes creates a conflict.
Rule 4: Odd cycles cause same-color conflicts; even cycles do not.
Rule 5: Every tree is bipartite because trees contain zero cycles.

Production Thinking

User-Role Access Control Validation → Verifying security boundaries between user entity groups and system role permissions

Driver-Ride Matching Dispatch → Bipartite matching between available rideshare drivers and rider requests

Server Task Scheduling → Allocating batch computing tasks to compatible worker servers

Student Course Assignment → Matching student elective preferences to available course slots

Remember This

Bipartite Graph  → 2 Groups
Colors           → 0 / 1 (-1 = uncolored)
Neighbor Color   → 1 - currentColor
Same Color Edge  → FAIL (Not Bipartite)
BFS / DFS        → Both work in O(V + E)
Odd Cycle        → NOT Bipartite
Even Cycle / Tree→ ALWAYS Bipartite
Disconnected     → Color every component
Time             → O(V + E)

💡 Golden Rule: "Give every neighbor the opposite color. If an edge ever connects two nodes with the same color, the graph is not bipartite."