Bipartite Matching

Quick Revisit

• USE WHEN: Assigning items to slots 1-to-1 optimally (job assignment, grid covering, independent set on bipartite graphs)
• INVARIANT: Matching is maximum iff no augmenting path exists (Berge's theorem)
• TIME: O(V × E) Kuhn's, O(E√V) Hopcroft-Karp | SPACE: O(V + E)
• CLASSIC BUG: Not resetting the visited array between augmenting-path searches in Kuhn's algorithm — causes false "no augmenting path" and suboptimal matching
• PRACTICE: 05-ladder-graphs

AL-25 | Maximum matching in bipartite graphs -- assign items to slots optimally using augmenting-path DFS (Kuhn) or the faster Hopcroft-Karp algorithm.

Difficulty: [Advanced]Prerequisites: DFS and Tree DFS. Max Flow / Min Cut is related (matching is a special case of flow) but not required to learn Kuhn. CF Rating Range: 1800-2200+

---

Intuition

You have 4 workers and 4 jobs. Each worker can perform some subset of jobs. Assign as many workers as possible to jobs, one-to-one (each worker gets at most one job, each job at most one worker).

  Workers        Jobs they can do
  -------        ----------------
  W1             JA, JB
  W2             JA, JC
  W3             JB, JC
  W4             JC, JD

Naive brute force: try every possible assignment permutation.

• 4 workers, 4 jobs --> at most $4!=24$ permutations to check.
• 10 workers, 10 jobs --> $10!=3628800$.
• 20 workers, 20 jobs --> $20!\approx 2.4\times {10}^{18}$.

This is $O(n!)$ -- completely hopeless for $n>15$.

We need an algorithm that finds the maximum matching in polynomial time.

Try to match each node greedily; when stuck, find an augmenting path through already-matched edges to "swap" assignments and increase the matching.

This is Kuhn's algorithm (also called the Hungarian DFS method).

Analogy -- dance partners. Imagine a school dance where boys stand on one side and girls on the other. Each boy has a list of girls he would dance with. You go through the boys one by one and try to pair each with an available girl. If every girl on his list already has a partner, you ask one of those girls' current partners: "Can you find a different girl?" If that boy can switch, the chain of swaps frees up a girl for the original boy. This chain of swaps is an augmenting path.

The algorithm runs in $O(V\cdot E)$ time -- polynomial and fast enough for most contest constraints ($V\le 5000$, $E\le {10}^5$).

Visual Walkthrough

Setup: 4 workers (W1..W4), 4 jobs (JA..JD), edges as above.

  W1 ------- JA
  W1 ------- JB
  W2 ------- JA
  W2 ------- JC
  W3 ------- JB
  W3 ------- JC
  W4 ------- JC
  W4 ------- JD

Step 1: Try to match W1.

W1 checks JA -- JA is free. Match W1 <=> JA.

  Matching: { W1=JA }   size = 1

Step 2: Try to match W2.

W2 checks JA -- JA is taken by W1. Can W1 find another partner? W1 checks JB -- JB is free. W1 switches to JB. Now JA is free. Match W2 <=> JA.

  Matching: { W1=JB, W2=JA }   size = 2

Step 3: Try to match W3.

W3 checks JB -- JB is taken by W1. Can W1 find another partner? W1 checks JA -- JA is taken by W2. Can W2 find another partner? W2 checks JC -- JC is free. W2 switches to JC. Now JA is free. W1 switches to JA. Now JB is free. Match W3 <=> JB.

Augmenting path found:

  W3 ---> JB ===> W1 ---> JA ===> W2 ---> JC
  (free)          (swap)          (swap)   (free!)

  Matching: { W1=JA, W2=JC, W3=JB }   size = 3

Step 4: Try to match W4.

W4 checks JC -- JC is taken by W2. Can W2 find another partner? W2 checks JA -- JA is taken by W1. Can W1 find another partner? W1 checks JB -- JB is taken by W3. Can W3 find another partner? W3 checks JC -- already visited this DFS. Dead end. W1 has no other options. Dead end. W2 has no other options. Dead end. W4 checks JD -- JD is free. Match W4 <=> JD.

  Matching: { W1=JA, W2=JC, W3=JB, W4=JD }   size = 4

Final maximum matching = 4. All workers assigned.

Augmenting Path Discovery

An augmenting path starts at an unmatched left node, alternates between unmatched and matched edges, and ends at an unmatched right node. Flipping every edge along the path increases the matching by 1.

  Current matching -- 2 edges         After augmenting path found
                                      
  L1 ------- R1                       L1 ------- R1
  L2 ******* R2   *matched*           L2         R2
  L3 ------- R2                       L3 ******* R2   *now matched*
  L3 ------- R3                       L2 ******* R1   *now matched*
                                      L3         R3
  -- unmatched    ** matched
                                      Path found by L3
  L3 is unmatched so we start DFS     L3 ---> R2 ***> L2 ---> R1
  from L3                               free   matched  free  free
                                      
                                      Flip all edges on the path
                                      L3-R2 becomes matched
                                      L2-R2 becomes unmatched
                                      L2-R1 becomes matched
                                      
                                      New matching size -- 3

AUGMENTING PATH CHAIN -- step-by-step visualization:

  Initial state: W1─J1, W2─J2 matched.  W3 unmatched.
  W3 wants J1 (occupied by W1).

  Step 1: W3 asks W1 to move
  ┌────┐        ┌────┐
  │ W3 │───?───->│ J1 │<-──matched──┐
  └────┘        └────┘            │
                                ┌────┐
                                │ W1 │
                                └────┘

  Step 2: W1 tries J2 (occupied by W2), asks W2 to move
  ┌────┐        ┌────┐
  │ W1 │───?───->│ J2 │<-──matched──┐
  └────┘        └────┘            │
                                ┌────┐
                                │ W2 │
                                └────┘

  Step 3: W2 tries J3 -- FREE!
  ┌────┐        ┌────┐
  │ W2 │───────->│ J3 │  <- unmatched, success!
  └────┘        └────┘

  Resolution (unwind the chain):
    W2─J3 (new),  W1─J2 (rerouted),  W3─J1 (rerouted)

  ┌────┐   ┌────┐   ┌────┐
  │ W3 │──->│ W1 │──->│ W2 │
  └────┘   └────┘   └────┘
    ↓        ↓        ↓
  ┌────┐   ┌────┐   ┌────┐
  │ J1 │   │ J2 │   │ J3 │
  └────┘   └────┘   └────┘

  Matching size: 2 -> 3  (increased by 1)

Konig Theorem -- Min Vertex Cover

In bipartite graphs max matching equals min vertex cover. A vertex cover is a set of nodes such that every edge has at least one endpoint in it.

  Maximum matching -- 3 edges        Minimum vertex cover -- 3 nodes
                                     
  L1 ******* R1                      L1 ******* R1   <-- pick R1
  L2 ******* R2                      L2 ******* R2   <-- pick L2
  L3 ******* R3                      L3 ******* R3   <-- pick L3
  L4 ------- R2                      L4 ------- R2
  L4 ------- R3                      L4 ------- R3
                                     
  ** matched  -- unmatched           Cover nodes -- R1 L2 L3
                                     Every edge has at least one
                                     endpoint in the cover
                                     
                                     #Cover# -- #Matching# -- 3

Maximum Independent Set

The complement of a vertex cover is an independent set. In bipartite graphs max independent set equals total nodes minus max matching.

  Vertex cover        Independent set -- complement
                      
  L1    #R1#          #L1#   R1         No edges between
  #L2#   R2           L2    #R2#        independent set
  #L3#   R3           L3    #R3#        members
  L4    ...           #L4#  ...
                      
  #x# -- in the set
                      
  +------------------------------------------+
  | #V Cover# + #Indep Set# -- #All Nodes#   |
  |    3      +      4       --     7         |
  +------------------------------------------+

Worked Example -- Kuhn on a 4+3 Graph

Run Kuhn step by step on 4 left nodes and 3 right nodes.

  Graph                    Adjacency
                           
  L1 ------- R1            L1 -- R1 R2
  L1 ------- R2            L2 -- R1 R3
  L2 ------- R1            L3 -- R2
  L2 ------- R3            L4 -- R2 R3
  L3 ------- R2
  L4 ------- R2
  L4 ------- R3

Round 1 -- try L1

  DFS from L1
    L1 -> R1   R1 is free
    Match L1-R1
  
  Matching     L1*R1                      size 1

Round 2 -- try L2

  DFS from L2
    L2 -> R1   taken by L1
      L1 -> R2   R2 is free -- L1 reroutes
      L1 takes R2
    L2 takes R1
  
  Augmenting path  L2 --> R1 **> L1 --> R2
  Matching     L2*R1  L1*R2               size 2

Round 3 -- try L3

  DFS from L3
    L3 -> R2   taken by L1
      L1 -> R1   taken by L2
        L2 -> R3   R3 is free -- L2 reroutes
        L2 takes R3
      L1 takes R1
    L3 takes R2
  
  Augmenting path  L3 --> R2 **> L1 --> R1 **> L2 --> R3
  Matching     L1*R1  L2*R3  L3*R2        size 3

Round 4 -- try L4

  DFS from L4
    L4 -> R2   taken by L3
      L3 has only R2 -- already visited -- dead end
    L4 -> R3   taken by L2
      L2 -> R1   taken by L1
        L1 -> R2   already visited -- dead end
      dead end
    L4 cannot be matched
  
  Matching unchanged                      size 3

Final matching -- size 3

  +-------+-------+
  | Left  | Right |
  +-------+-------+
  |  L1   *  R1   |
  |  L2   *  R3   |
  |  L3   *  R2   |
  |  L4   *  ---  |
  +-------+-------+
  3 out of 4 left nodes matched
  This is maximum -- L4 cannot reach
  any right node without conflict

The Invariant

+------------------------------------------------------------------+
| INVARIANT                                                        |
|                                                                  |
| 1. The matching is always VALID: no node appears in more than    |
|    one matched edge.                                             |
|                                                                  |
| 2. Each augmenting path increases the matching size by exactly   |
|    1. (It starts and ends at unmatched nodes, and flipping       |
|    matched/unmatched edges along it adds one net edge.)          |
|                                                                  |
| 3. When no augmenting path exists for any remaining unmatched    |
|    left node, the matching is MAXIMUM. (Berge's theorem.)        |
+------------------------------------------------------------------+

Why this guarantees optimality: By Berge's theorem, a matching $M$ is maximum if and only if there is no $M$-augmenting path. Kuhn's algorithm terminates only when no augmenting path can be found from any unmatched left node, so the result is a maximum matching.

When to Reach for This

Trigger phrases in problem statements:

• "maximum matching" or "maximum assignment"
• "assign workers to jobs" / "assign students to courses"
• "bipartite graph"
• "minimum vertex cover" (equals max matching by Konig's theorem)
• "maximum independent set" on a bipartite graph ($=|V|-\text{max matching}$)
• "minimum rows + columns to cover all marked cells in a grid"
• "place maximum non-attacking rooks on a board with obstacles"

Counter-examples -- when this is NOT the right tool:

• The graph is not bipartite. Kuhn silently gives wrong answers on general graphs. Use Edmonds' blossom algorithm or Tutte matrix instead.
• You need a weighted maximum matching (maximize total weight, not count). Use the Hungarian algorithm ($O(n^3)$) or min-cost max-flow.
• The assignment has capacities (a job can take multiple workers). This is a flow problem, not a matching problem.
• $n\le 20$ and the structure is complex -- consider bitmask DP instead.

Decision Flowchart

  START: "I need to assign/match things"
    |
    v
  Is the graph bipartite?
    |             |
   YES            NO
    |             |
    v             v
  N <= 5000?    N <= 20?
    |    |        |    |
   YES   NO      YES   NO
    |     |       |     |
    v     v       v     v
  Kuhn  Hopcroft  Bitmask  Blossom /
  O(VE) -Karp     DP       Tutte matrix
        O(E√V)    O(2^n*n)
    |
    v
  Need minimum weight?
    |          |
   YES         NO
    |          |
    v          v
  Hungarian   Done -- Kuhn / Hopcroft
  O(n³) or    gives max-cardinality
  min-cost    matching
  max-flow

What the Code Won't Teach You

Problem recognition is the real skill. The Kuhn DFS is 15 lines. Writing it takes 2 minutes. Recognizing that "place maximum non-attacking rooks on a board with obstacles" is bipartite matching -- rows on one side, columns on the other, obstacle-free cells as edges -- takes the experience of having seen it before. Build a library of reductions in your head:

REDUCTION CHEAT SHEET -- "Is This Secretly Matching?"
+-------------------------------+-------------------------------+
| Problem phrasing              | Matching model                |
+-------------------------------+-------------------------------+
| Assign items to slots 1:1     | Direct matching               |
| Max non-attacking rooks       | Row-col bipartite graph       |
| Min path cover in DAG         | n - max matching              |
| Max independent set (bip.)    | n - max matching (König)      |
| Min vertex cover (bip.)       | = max matching   (König)      |
| Min rows+cols covering marks  | Min vertex cover = matching   |
+-------------------------------+-------------------------------+

A maximum matching is not unique. Kuhn's finds a maximum matching, but the specific edges depend on the order left nodes are processed. Multiple maximum matchings may exist. If the problem asks "is edge $(u,v)$ in every maximum matching?" you need additional analysis beyond just running Kuhn once.

Know when matching is the wrong hammer. Three common disguises: (1) Each slot accepts $k>1$ items -> flow with capacities, not matching. (2) Minimize total weight of the assignment -> Hungarian algorithm or min-cost max-flow, not maximum-cardinality matching. (3) The conflict graph has odd cycles -> not bipartite, Kuhn silently gives wrong answers. You need Edmonds' blossom algorithm.

The Hall's theorem connection. A complete matching of the left side exists if and only if for every subset $S$ of left vertices, the neighborhood $N(S)$ has $|N(S)|\ge |S|$. The code finds a maximum matching but never checks Hall's condition explicitly -- yet this condition is why the matching exists (or doesn't). When a problem asks "is a perfect matching possible?", Hall's theorem often gives a cleaner proof than running the algorithm.

   HALL'S MARRIAGE THEOREM -- visual check:
   
   LEFT     RIGHT          Hall's condition:
   ┌──┐     ┌──┐           For every subset S ⊆ LEFT,
   │L1│────->│R1│           |N(S)| >= |S|
   │  │╲    │  │
   └──┘ ╲   └──┘           Check S = {L1, L2}:
   ┌──┐  ╲  ┌──┐             N({L1,L2}) = {R1,R2,R3}
   │L2│───->->│R2│             |N| = 3 >= 2 = |S|  OK
   │  │╲    │  │
   └──┘ ╲   └──┘           Check S = {L1, L2, L3}:
   ┌──┐  ╲  ┌──┐             N({L1,L2,L3}) = {R1,R2,R3}
   │L3│────->│R3│             |N| = 3 >= 3 = |S|  OK
   └──┘     └──┘
                            All subsets pass -> perfect
                            matching EXISTS (Hall's thm)

The minimum path cover reduction. In a DAG, minimum path cover = $n$ - maximum matching on the split graph (each node $v$ becomes $v_{\text{out}}$ on the left and $v_{\text{in}}$ on the right; edge $u\to v$ becomes $u_{\text{out}}\leftrightarrow v_{\text{in}}$). The code gives you the matching; the insight is recognizing that "cover all nodes with minimum paths" is secretly a matching problem on a transformed graph.

---

C++ STL Reference

Bipartite matching is not directly in the STL, but these containers are used in every implementation:

Function / Class	Header	What it does	Time Complexity
vector<vector<int>> adj	<vector>	Adjacency list for left-to-right edges	$O(1)$ per access
vector<int> match_l, match_r	<vector>	match_l[u] = right node matched to left node $u$ ($-1$ if free)	$O(1)$ per access
vector<bool> used	<vector>	Visited flags for current DFS augmenting path search	$O(1)$ per access
fill(used.begin(), used.end(), false)	<algorithm>	Reset visited array between Kuhn DFS calls	$O(n)$
queue<int>	<queue>	BFS layer discovery in Hopcroft-Karp	$O(1)$ push/pop
vector<int> dist	<vector>	BFS distances in Hopcroft-Karp	$O(1)$ per access

---

Implementation (Contest-Ready)

Version 1: Kuhn's Algorithm -- Minimal Template

#include <bits/stdc++.h>
using namespace std;

int n, m, k; // |L|, |R|, |edges|
vector<int> adj[5001];
int match_r[5001];
bool used[5001];

bool dfs(int u) {
    for (int v : adj[u]) {
        if (!used[v]) {
            used[v] = true;
            if (match_r[v] == -1 || dfs(match_r[v])) {
                match_r[v] = u;
                return true;
            }
        }
    }
    return false;
}

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
    }
    memset(match_r, -1, sizeof match_r);
    int ans = 0;
    for (int u = 1; u <= n; u++) {
        memset(used, false, sizeof used);
        if (dfs(u)) ans++;
    }
    cout << ans << "\n";
}

Version 2: Kuhn's Algorithm -- Explained

#include <bits/stdc++.h>
using namespace std;

// Left nodes: 1..n, Right nodes: 1..m
// adj[u] = list of right nodes that left node u can match to
int n, m, k;
vector<int> adj[5001];
int match_r[5001]; // match_r[v] = which left node is matched to right node v (-1 if free)
bool used[5001];   // visited flags for current DFS call

// Try to find an augmenting path starting from left node u.
// Returns true if u can be matched (possibly by re-matching others).
bool dfs(int u) {
    for (int v : adj[u]) {
        if (!used[v]) {
            used[v] = true;
            // If right node v is free, or its current match can find another partner:
            if (match_r[v] == -1 || dfs(match_r[v])) {
                match_r[v] = u; // assign v to u
                return true;
            }
        }
    }
    return false; // no augmenting path from u
}

int main() {
    cin >> n >> m >> k;
    for (int i = 0; i < k; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); // edge from left u to right v
    }

    memset(match_r, -1, sizeof match_r);

    int ans = 0;
    for (int u = 1; u <= n; u++) {
        // Reset visited for each left node's DFS.
        // This is the "used" array that prevents revisiting
        // right nodes within a single augmenting-path search.
        memset(used, false, sizeof used);
        if (dfs(u)) ans++;
    }

    cout << ans << "\n";

    // To print the matching:
    // for (int v = 1; v <= m; v++)
    //     if (match_r[v] != -1)
    //         cout << match_r[v] << " " << v << "\n";
}

When Kuhn is enough vs when you need Hopcroft-Karp

In contest practice the distinction is purely about constraints:

• Kuhn ($O(VE)$) is enough when one side has $V\le 5000$ and edges $E\le {10}^5$ -- a few times ${10}^8$ in the worst case, fast enough at 1-2 seconds. This covers the majority of bipartite-matching CF problems and almost all CSES bipartite tasks.
• Hopcroft-Karp ($O(E\sqrt{V})$) is required when $V$ approaches ${10}^5$ or edges reach ${10}^6$. The constant factor is small; the speedup comes from layering augmenting paths in BFS phases.
• Min-cost / weighted matching is a different algorithm entirely (Hungarian or MCMF -- see lesson 07). Kuhn does not generalize to costs.
• Online or dynamic matching is also outside Kuhn's scope; for problems where edges arrive over time, see specialised structures.

If you are unsure, write Kuhn first. It has a 15-line core and is much easier to debug. Switch to Hopcroft-Karp only if Kuhn TLEs on the given constraints.

Version 3: Hopcroft-Karp -- $O(E\sqrt{V})$

Use when $|V|$ or $|E|$ exceeds $\sim {10}^5$.

#include <bits/stdc++.h>
using namespace std;

struct HopcroftKarp {
    int n, m;
    vector<vector<int>> adj;
    vector<int> match_l, match_r, dist;

    HopcroftKarp(int n, int m) : n(n), m(m), adj(n), match_l(n, -1), match_r(m, -1), dist(n) {}

    void add_edge(int u, int v) { adj[u].push_back(v); }

    bool bfs() {
        queue<int> q;
        for (int u = 0; u < n; u++) {
            if (match_l[u] == -1) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = INT_MAX;
            }
        }
        bool found = false;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                int w = match_r[v];
                if (w == -1) {
                    found = true;
                } else if (dist[w] == INT_MAX) {
                    dist[w] = dist[u] + 1;
                    q.push(w);
                }
            }
        }
        return found;
    }

    bool dfs(int u) {
        for (int v : adj[u]) {
            int w = match_r[v];
            if (w == -1 || (dist[w] == dist[u] + 1 && dfs(w))) {
                match_l[u] = v;
                match_r[v] = u;
                return true;
            }
        }
        dist[u] = INT_MAX;
        return false;
    }

    int max_matching() {
        int ans = 0;
        while (bfs())
            for (int u = 0; u < n; u++)
                if (match_l[u] == -1 && dfs(u))
                    ans++;
        return ans;
    }
};

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    HopcroftKarp hk(n, m);
    for (int i = 0; i < k; i++) {
        int u, v;
        cin >> u >> v;
        hk.add_edge(u - 1, v - 1); // 0-indexed
    }
    cout << hk.max_matching() << "\n";
}

---

Operations Reference

Operation	Time	Space
Kuhn's algorithm (full matching)	$O(V\cdot E)$	$O(V+E)$
Single augmenting path DFS	$O(E)$	$O(V)$ stack
Hopcroft-Karp (full matching)	$O(E\sqrt{V})$	$O(V+E)$
Hopcroft-Karp single BFS phase	$O(V+E)$	$O(V)$
Minimum vertex cover (via Konig)	$O(V+E)$ after matching	$O(V)$
Maximum independent set	$O(1)$ after matching	--

Practical guidance:

• $|V|\le 5000,|E|\le {10}^5$: Kuhn is fine.
• $|V|\le {10}^5,|E|\le {10}^6$: Use Hopcroft-Karp.
• $|V|\le 500$: Even $O(V^3)$ Hungarian works.

BIPARTITE MATCHING AS FLOW NETWORK:

  source ──(cap 1)──-> L1 ──(cap 1)──-> R1 ──(cap 1)──-> sink
  source ──(cap 1)──-> L2 ──(cap 1)──-> R2 ──(cap 1)──-> sink
  source ──(cap 1)──-> L3 ──(cap 1)──-> R3 ──(cap 1)──-> sink
  source ──(cap 1)──-> L4             R4 ──(cap 1)──-> sink

  Cross edges (bipartite edges, cap 1):
    L1->R1, L1->R3
    L2->R2, L2->R4
    L3->R1, L3->R2
    L4->R3

            ┌────┐         ┌────┐
    ┌──────->│ L1 │────────->│ R1 │──────┐
    │       └────┘╲        └────┘      │
    │              ╲                    │
    │       ┌────┐  ╲      ┌────┐      │
    │  ┌───->│ L2 │───╲────->│ R2 │──┐   │
    │  │    └────┘    ╲    └────┘  │   │
  ┌─┤  │               ╲          │   ├─┐
  │ S│  │    ┌────┐      ╲ ┌────┐  │   │T│
  │  │  ├───->│ L3 │───────->│ R3 │──┤   │ │
  └─┤  │    └────┘        └────┘  │   ├─┘
    │  │                           │   │
    │  │    ┌────┐        ┌────┐   │   │
    │  └───->│ L4 │───────->│ R4 │───┘   │
    │       └────┘        └────┘       │
    └──────────────────────────────────┘

  Max flow = max matching.
  Dinic's on this graph: O(E√V).

---

Problem Patterns & Tricks

Pattern 1: Direct Assignment Problem

The problem literally says "assign X to Y, maximize count." Build bipartite graph and run matching.

Example: $n$ students, $m$ courses, each student has a preference list. Maximize enrolled students.

Problems: CF 1598D -- Training Session, CF 1139E -- Maximize Mex

---

Pattern 2: Minimum Vertex Cover (Konig's Theorem)

"Find the minimum number of rows + columns to cover all marked cells in a grid." This is minimum vertex cover in a bipartite graph where rows are left nodes, columns are right nodes, and marked cells are edges.

By Konig: $\text{min vertex cover}=\text{max matching}$.

// Grid with marked cells: row i, col j marked -> edge (i, j)
// Min vertex cover = max bipartite matching
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
        if (grid[i][j] == '#')
            adj[i].push_back(j);
// Run Kuhn -> answer is matching size

Problems: CF 1198E -- Rectangle Painting 2, CF 2039E -- Shohag Loves Counting

---

Pattern 3: Maximum Independent Set

"Find the maximum set of elements with no conflicts." If the conflict graph is bipartite:

$$\text{max independent set}=|V|-\text{max matching}$$

Example: Place maximum non-attacking rooks on a chessboard with blocked cells. Each rook "attacks" a row and a column -- bipartite graph where rows/columns are sides.

Problems: CF 1593F -- Red-Blue Graph

---

Pattern 4: Grid Problems -- Rook/Bishop/Knight Placement

Many grid placement problems reduce to bipartite matching. Typical pattern: color cells like a checkerboard, then cells of one color form one side, cells of the other color form the other.

Knight domination on grid: Two cells a knight can jump between always have different parity. So the knight-move graph on a grid is bipartite.

Problems: CF 1404E -- Bricks

---

Pattern 5: Hall's Theorem Check

Hall's marriage theorem: a perfect matching from $L$ to $R$ exists iff for every subset $S\subseteq L$, $|N(S)|\ge |S|$ (where $N(S)$ is the set of neighbors of $S$).

In contests, Hall's theorem is used to prove a matching exists or to find the bottleneck subset. Rarely implemented directly -- usually you just run Kuhn and check if matching size $=|L|$.

Problems: CF 981D -- Bookshelves

---

Pattern 6: Matching with Modifications (Online / Weighted)

• Online matching: Nodes arrive one at a time. Greedily match or use Kuhn with re-augmenting.
• Weighted matching: Use the Hungarian algorithm ($O(n^3)$) or min-cost max-flow. Beyond basic Kuhn but often needed at 2200+.

Problems: CF 1728G -- Illumination

---

Pattern 7: Reduction from 2-coloring / Bipartiteness

First check if the graph is bipartite (BFS/DFS 2-coloring). If yes, matching-related theorems apply. If not, the problem needs a different approach (e.g., Tutte matrix for general matching).

Tip: If the problem constraints are small ($n\le 20$), consider bitmask DP over matchings instead of Kuhn.

Problems: CF 1016F -- Road Projects

---

Contest Cheat Sheet

+------------------------------------------------------------------+
|                 BIPARTITE MATCHING CHEAT SHEET                   |
+------------------------------------------------------------------+
| WHEN TO USE:                                                     |
|   - Assign items to slots, maximize assignments                  |
|   - "Min rows + cols to cover all marks" (Konig)                 |
|   - "Max non-conflicting set" on bipartite conflict graph        |
|   - Grid placement with parity-based coloring                    |
+------------------------------------------------------------------+
| KUHN (copy-paste core):                                          |
|   bool dfs(int u) {                                              |
|       for (int v : adj[u]) if (!used[v]) {                       |
|           used[v] = 1;                                           |
|           if (mt[v]==-1 || dfs(mt[v])) { mt[v]=u; return 1; }   |
|       }                                                          |
|       return 0;                                                  |
|   }                                                              |
|   // For each u in L: reset used[], call dfs(u).                 |
+------------------------------------------------------------------+
| KONIG:  min vertex cover  = max matching                         |
|         max indep. set    = |V| - max matching                   |
+------------------------------------------------------------------+
| COMPLEXITY:                                                      |
|   Kuhn:          O(V * E)         | V <= 5000                    |
|   Hopcroft-Karp: O(E * sqrt(V))   | V <= 100000                  |
+------------------------------------------------------------------+

---

Gotchas & Debugging

Forgetting to reset used[] between DFS calls

The used array must be cleared before each call to dfs(u) for a new left node. Forgetting this is the #1 Kuhn bug -- you'll get a matching that's too small.

0-indexed vs 1-indexed confusion

Kuhn uses match_r[v] = -1 for "unmatched." If your nodes are 1-indexed but you initialize match_r to 0, every right node looks matched to node 0. Use -1 consistently.

Building the wrong bipartite graph

The most common conceptual error. Double-check:

• What are the left nodes? Right nodes?
• When does an edge exist?
• Is the graph actually bipartite? (If not, Kuhn silently gives wrong answers.)

Kuhn TLE on dense graphs

Kuhn is $O(V\cdot E)$. For $V=5000,E=V^2=25\times {10}^6$, total work is $\sim {10}^{10}$ -- too slow. Switch to Hopcroft-Karp or reduce the graph.

Randomize left-node order to improve Kuhn's practical performance:

vector<int> order(n);
iota(order.begin(), order.end(), 1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
shuffle(order.begin(), order.end(), rng);
for (int u : order) {
    memset(used, false, sizeof used);
    if (dfs(u)) ans++;
}

Reconstructing the matching

Kuhn naturally stores it: match_r[v] gives the left node matched to right node $v$. If you also need match_l[u], maintain it in the DFS:

if (match_r[v] == -1 || dfs(match_r[v])) {
    match_r[v] = u;
    match_l[u] = v; // add this
    return true;
}

Konig reconstruction

To find the actual minimum vertex cover (not just its size), run BFS/DFS from unmatched left nodes along alternating paths, then:

• Include left nodes not reached by the alternating BFS.
• Include right nodes reached by the alternating BFS.

Edge case: empty graph

If $|L|=0$ or $|R|=0$ or no edges, matching is 0. Make sure your code handles this without crashing.

Debug checklist

1. Print the adjacency list -- verify edges are correct.
2. Print match_r[] after each augmentation -- matching should grow by 1 each time.
3. Test on a small hand-drawn bipartite graph where you know the answer.
4. If matching is too small, check used[] reset and edge directions.

Mental Traps

"I see two groups of objects, so the graph must be bipartite."

Two groups in the problem statement do not guarantee bipartiteness of the conflict graph. The matching graph must have edges only between the two sides, never within a side. If same-side conflicts exist, Kuhn silently returns wrong answers. Always verify the 2-coloring.

  CORRECT bipartite setup          WRONG -- edge within one side

  Workers       Jobs               Students     Students
   W1 -------- JA                    S1 -------  S2
   W2 -------- JB                    S1 -------  S3
   W3 -------- JC                    S2 -------  S3
                                       ^--- NOT BIPARTITE
  Edges cross sides only.           Kuhn gives WRONG answer here.
  Kuhn works perfectly.             Need general matching (Blossom).

"König's theorem gives me the minimum vertex cover for free -- in any graph."

König's theorem ($\text{min vertex cover}=\text{max matching}$) holds only in bipartite graphs. In general graphs the minimum vertex cover is NP-hard. Applying König to a non-bipartite graph produces a number that is too small. If the problem graph has an odd cycle, stop -- König does not apply.

  Bipartite -- König works          General graph -- König FAILS

  L1 **** R1                          A ---- B
  L2 **** R2                          |  \   |
  L3 **** R3                          C ---- D
                                       \  /
  max matching = 3                      E
  min vertex cover = 3 OK
                                      max matching = 2
  König: cover = matching             König would say cover = 2
                                      TRUE min cover = 3  X

Trap 3: "Maximum matching = maximum independent set."

These are complementary, not equal. In a bipartite graph with $n$ vertices, maximum independent set = $n$ - maximum matching (by König's theorem). Confusing the two gives answers that are off by the matching size. Always double-check which quantity the problem asks for.

   KÖENIG'S THEOREM RELATIONSHIPS:
   
     Max Matching         Min Vertex Cover       Max Independent Set
         M        =            M         =         n - M
   
     ┌───────────────────────────────────────────────────────┐
     │                                                       │
     │   Workers ●──────● Jobs      MATCHING (M=3):          │
     │           ●──────●           3 edges, no shared vertex│
     │           ●──────●                                    │
     │           ●      ●                                    │
     │                                                       │
     │   VERTEX COVER = 3:    INDEPENDENT SET = 8 - 3 = 5:  │
     │   cover = matched      indep = unmatched + one side   │
     │   endpoints on one     of each matched pair           │
     │   side of each edge                                   │
     └───────────────────────────────────────────────────────┘

Trap 4: "If I process left nodes in a different order, I get a different matching size."

Kuhn's algorithm always finds a maximum matching regardless of processing order -- the augmenting-path method guarantees this via Berge's theorem. The specific matched pairs may differ, but the size is always optimal. If you're getting different sizes from different orderings, your used[] reset is buggy.

   ORDER INDEPENDENCE OF MAXIMUM MATCHING:
   
   Processing order 1:          Processing order 2:
   L1->R2, L2->R1, L3->R3         L3->R1, L1->R2, L2->R3
   
   Both find matching size = 3:
   
   Order 1:  L1─R2   L2─R1   L3─R3
   Order 2:  L3─R1   L1─R2   L2─R3
                                      <- different edges,
                                         SAME SIZE
   
   If sizes differ -> bug in used[] reset or DFS

---

Common Mistakes

1. Forgetting to reset used[] between augmenting-path searches. Kuhn's algorithm finds a matching of size 3 when the true maximum is 4 because, after successfully augmenting from vertex $u_1$, the used[] marks persist -- blocking the DFS from $u_2$ from visiting vertices that could lead to a valid augmenting path. Fix: memset(used, false, sizeof(used)) before each call to try_kuhn(v).

Debug Drills

Drill 1 -- Kuhn's DFS: not resetting visited array

int max_matching = 0;
for (int v = 0; v < n; v++) {
    // missing: fill(used, used + m, false);
    if (try_kuhn(v))
        max_matching++;
}

What's wrong?

The used[] array must be cleared before each augmenting-path search. Without it, the DFS from vertex v sees stale visited marks from previous iterations and fails to find valid augmenting paths:

for (int v = 0; v < n; v++) {
    fill(used, used + m, false);
    if (try_kuhn(v))
        max_matching++;
}

Drill 2 -- König's vertex cover: taking wrong side

// After max matching, build vertex cover:
// BFS from unmatched LEFT vertices
// Take VISITED left vertices + UNVISITED right vertices  // BUG

What's wrong?

König's theorem says: take unvisited left vertices + visited right vertices (where "visited" means reachable from unmatched left vertices via alternating paths). The rule is: for left, take those NOT in the BFS tree; for right, take those IN the BFS tree.

Drill 3 -- Match array stores left->right but DFS checks right->left

bool try_kuhn(int v) {
    for (int to : adj[v]) {
        if (!used[to]) {
            used[to] = true;
            if (match[v] == -1 || try_kuhn(match[v])) {  // BUG: match[v] wrong
                match[v] = to;
                return true;
            }
        }
    }
    return false;
}

What's wrong?

match should be indexed by right-side vertices: match[to] = the left vertex currently matched to right vertex to. The check should be match[to] == -1 || try_kuhn(match[to]):

if (match[to] == -1 || try_kuhn(match[to])) {
    match[to] = v;
    return true;
}

Self-Test

Before moving to practice problems, verify you can answer these without looking at the notes:

• [ ] Write Kuhn's augmenting-path DFS from memory -- including the used[] reset before each left-node's DFS call.
• [ ] State König's theorem and its scope -- minimum vertex cover equals maximum matching, but only in bipartite graphs.
• [ ] Given a grid problem "minimum rows + columns to cover all marked cells," model it as bipartite matching: rows = left nodes, columns = right nodes, marked cells = edges.
• [ ] Explain why Kuhn's algorithm produces a maximum matching (not just maximal) -- cite Berge's theorem: no augmenting path ⟹ matching is maximum.
• [ ] Identify when to switch from Kuhn ($O(VE)$, $V\le 5000$) to Hopcroft-Karp ($O(E\sqrt{V})$, $V\le {10}^5$) based on constraint sizes.
• [ ] Given a bipartite graph with 4 left and 5 right nodes, trace Kuhn's algorithm step-by-step, showing the used[] reset between each left node's DFS and the augmenting-path chain when a reroute occurs.
• [ ] State König's theorem and compute the minimum vertex cover size from a maximum matching of size 5 in a bipartite graph with 12 vertices.
• [ ] Model the "minimum path cover in a DAG" problem: draw the split graph for a 4-node DAG and explain why the answer is $n$ minus the matching size.
• [ ] Explain why Kuhn's algorithm is $O(VE)$ and Hopcroft-Karp is $O(E\sqrt{V})$ -- what structural difference in the BFS-layered approach gives the speedup?
• [ ] Given a grid where some cells are blocked, reduce "place maximum non-attacking rooks" to bipartite matching by defining the two sides as rows and columns.

---

Practice Problems

CF Rating	What You Should Be Able to Do
1200	Identify bipartite structure; solve matching by brute force for small graphs.
1500	Implement Kuhn's $O(VE)$ algorithm; find maximum bipartite matching.
1800	Apply König's theorem for minimum vertex cover; model grid/assignment problems as bipartite matching.
2100	Use Hopcroft-Karp for $O(E\sqrt{V})$; combine matching with DP, flow, or incremental re-augmenting.

#	Problem	Source	Difficulty	Key Idea
1	CSES School Dance	CSES	1600	Direct bipartite matching, Kuhn template
2	CF 1139E -- Maximize Mex	CF	1800	Online matching with re-augmenting
3	CF 1404E -- Bricks	CF	2000	Grid matching, min vertex cover via Konig
4	CF 1198E -- Rectangle Painting 2	CF	2000	Flow / matching on coordinate-compressed grid
5	CF 1728G -- Illumination	CF	2100	Matching with combinatorial counting
6	CF 1593F -- Red-Blue Graph	CF	2100	Max independent set via Konig
7	CF 741C -- Arpa's overnight party	CF	2200	Bipartite matching with additional constraints
8	CSES Coin Grid	CSES	1800	Min vertex cover on grid = max matching

---

Further Reading

• cp-algorithms: Kuhn's Algorithm -- clean explanation with proof of correctness.
• cp-algorithms: Hopcroft-Karp -- faster algorithm with BFS + DFS phases.
• CF Blog: Bipartite Matching and Konig's Theorem -- community guide with contest examples.
• CF Blog: Maximum matching, flows, and more -- connections between matching and network flow.
• Prerequisite: Max Flow / Min Cut
• Prerequisite: DFS and Tree DFS
• Related: Graph Representation