SyntaxPilot
Courses/Competitive Programming/Lesson 59
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 59 of 90

Bipartite matching and König's theorem

queued

These are the notes for Competitive Programming episode 59. A bipartite graph has two sides with edges only going across; a matching is a set of edges with no shared endpoint, and we want the maximum matching. Interns and Projects shows that "each intern takes the first free project" is wrong (3 where 4 is possible) and that trying every assignment is exponential (Time Limit Exceeded). An augmenting path (a chain of "can you move, please?" requests from a free intern to a free project) adds one pair; Kuhn's algorithm runs one such search per intern in O(L · k). Without the asked[] mark the search recurses forever: Runtime Error (SIGSEGV). Mop the Spills turns rows and columns into a bipartite graph: the fewest mops is a minimum vertex cover, and by König's theorem it equals the maximum matching; the greedy "mop the fullest line" uses 4 where 3 is enough, and the cover is built by an alternating walk from the unmatched rows. Stress tests pass. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

An office has interns and projects. Intern 2 only wants project 1, but intern 1 already has it. Intern 2 asks: "could you move to another project you'd accept?" Intern 1 would take project 2, which intern 3 has, so intern 1 asks intern 3, and so on, until somebody finds a free project. Then everyone on the chain shifts by one: nobody loses a project, and one more intern is placed. One rule keeps this from going round in circles: in one search, never ask about the same project twice.

Definitions

  • Bipartite graph: vertices split into a left side and a right side; every edge joins a left vertex to a right vertex.
  • Matching: a set of edges, no two sharing a vertex. Maximum matching: the largest. Perfect matching: every vertex matched.
  • Alternating path: a path whose edges are alternately outside and inside the matching.
  • Augmenting path: an alternating path from a free left vertex to a free right vertex. Flipping it (in ↔ out) grows the matching by 1.
  • Berge's theorem: a matching is maximum exactly when no augmenting path exists.
  • Vertex cover: a set of vertices touching every edge. König's theorem: in a bipartite graph, minimum vertex cover = maximum matching.

Problem G1 · Interns and Projects

(Written for this course, in the style of a classic matching problem.)

  • Input: L R k (L, R ≤ 1000, k ≤ 10^5), then k lines u p ("intern u would accept project p").
  • Output: the most interns that can be given a project (each project to at most one intern).
4 4 7
1 1
1 2
2 1
3 2
3 3
4 3
4 4
Intern Accepts
1 1, 2
2 1
3 2, 3
4 3, 4

The answer is 4: 1–2, 2–1, 3–3, 4–4.

The obvious attempt: first free project (WA)

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

int L, R, k, owner[1001];                      // owner[p] = intern on project p (0 = free)
vector<int> likes[1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> L >> R >> k;
    for (int i = 0; i < k; i++) {
        int u, p;
        cin >> u >> p;
        likes[u].push_back(p);
    }
    int pairs = 0;
    for (int u = 1; u <= L; u++)
        for (int p : likes[u])
            if (owner[p] == 0) {                 // first free project
                owner[p] = u;
                pairs++;
                break;
            }
    cout << pairs << "\n";
}
3

Intern 1 takes project 1, intern 2 finds nothing free, 3 takes 2, 4 takes 3: 3 pairs.

The safe attempt: try every assignment (TLE)

For every intern either skip them or try each free project they like, and keep the best total.

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

int L, R, k, owner[1001];                      // owner[p] = intern on project p (0 = free)
vector<int> likes[1001];
bool taken[1001];
int best = 0;
void go(int u, int cnt) {                    // intern u: skip, or take a free project
    if (u > L) { best = max(best, cnt); return; }
    go(u + 1, cnt);
    for (int p : likes[u])
        if (!taken[p]) {
            taken[p] = true;
            go(u + 1, cnt + 1);
            taken[p] = false;
        }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> L >> R >> k;
    for (int i = 0; i < k; i++) {
        int u, p;
        cin >> u >> p;
        likes[u].push_back(p);
    }
    go(1, 0);
    cout << best << "\n";
}
4

With 1000 interns, 1000 projects and 2000 random likes, the search tree is exponential:

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

int L, R, k, owner[1001];                      // owner[p] = intern on project p (0 = free)
vector<int> likes[1001];
bool taken[1001];
int best = 0;
void go(int u, int cnt) {                    // intern u: skip, or take a free project
    if (u > L) { best = max(best, cnt); return; }
    go(u + 1, cnt);
    for (int p : likes[u])
        if (!taken[p]) {
            taken[p] = true;
            go(u + 1, cnt + 1);
            taken[p] = false;
        }
}

int main() {
    L = R = 1000, k = 2000;                 // 1000 interns, 1000 projects, 2000 likes
    mt19937 rng(59);
    for (int i = 0; i < k; i++) {
        int u = rng() % L + 1;
        likes[u].push_back(rng() % R + 1);
    }
    go(1, 0);
    cout << best << "\n";
}
Time Limit Exceeded

Kuhn's algorithm

tryIntern(u) looks at u's projects; a project p works if it is free, or if its owner can be moved (recursively) to another project. asked[p] makes sure each project is examined at most once per search; it is cleared before each intern's search. If the search succeeds, the assignments along the chain are flipped automatically by owner[p] = u on the way back. One search costs O(k), so the whole algorithm is O(L · k).

Why it finds the maximum. If no augmenting path starts at u now, none will start at u later either (a standard lemma), so skipping u is safe; and by Berge's theorem, when no augmenting path is left the matching is maximum.

The bug: no asked[] mark

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

int L, R, k, owner[1001];                      // owner[p] = intern on project p (0 = free)
vector<int> likes[1001];
bool asked[1001];
bool tryIntern(int u) {                      // find u a project, moving others if needed
    for (int p : likes[u])
        if (owner[p] == 0 || tryIntern(owner[p])) {   // free, or its owner can move
            owner[p] = u;
            return true;
        }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> L >> R >> k;
    for (int i = 0; i < k; i++) {
        int u, p;
        cin >> u >> p;
        likes[u].push_back(p);
    }
    int pairs = 0;
    for (int u = 1; u <= L; u++) {
        if (tryIntern(u)) pairs++;
    }
    cout << pairs << "\n";
}
Runtime Error (SIGSEGV)
Segmentation fault

Intern 2 asks intern 1 to move; intern 1 looks at project 1 first (its own), asks its owner (itself) to move, and so on forever, until the stack overflows. With the mark:

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

int L, R, k, owner[1001];                      // owner[p] = intern on project p (0 = free)
vector<int> likes[1001];
bool asked[1001];
bool tryIntern(int u) {                      // find u a project, moving others if needed
    for (int p : likes[u])
        if (!asked[p]) {
            asked[p] = true;                     // ask each project once per search
            if (owner[p] == 0 || tryIntern(owner[p])) {
                owner[p] = u;
                return true;
            }
        }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> L >> R >> k;
    for (int i = 0; i < k; i++) {
        int u, p;
        cin >> u >> p;
        likes[u].push_back(p);
    }
    int pairs = 0;
    for (int u = 1; u <= L; u++) {
        fill(asked, asked + R + 1, false);
        if (tryIntern(u)) pairs++;
    }
    cout << pairs << "\n";
}
4

No likes at all:

0

1000 × 1000 with 2000 random likes:

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

int L, R, k, owner[1001];                      // owner[p] = intern on project p (0 = free)
vector<int> likes[1001];
bool asked[1001];
bool tryIntern(int u) {                      // find u a project, moving others if needed
    for (int p : likes[u])
        if (!asked[p]) {
            asked[p] = true;                     // ask each project once per search
            if (owner[p] == 0 || tryIntern(owner[p])) {
                owner[p] = u;
                return true;
            }
        }
    return false;
}

int main() {
    L = R = 1000, k = 2000;                 // 1000 interns, 1000 projects, 2000 likes
    mt19937 rng(59);
    for (int i = 0; i < k; i++) {
        int u = rng() % L + 1;
        likes[u].push_back(rng() % R + 1);
    }
    int pairs = 0;
    for (int u = 1; u <= L; u++) {
        fill(asked, asked + R + 1, false);
        if (tryIntern(u)) pairs++;
    }
    cout << pairs << "\n";
}
772

Stress test against the brute force

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

int L, R, k, owner[1001];                      // owner[p] = intern on project p (0 = free)
vector<int> likes[1001];
bool taken[1001];
int best = 0;
void go(int u, int cnt) {                    // intern u: skip, or take a free project
    if (u > L) { best = max(best, cnt); return; }
    go(u + 1, cnt);
    for (int p : likes[u])
        if (!taken[p]) {
            taken[p] = true;
            go(u + 1, cnt + 1);
            taken[p] = false;
        }
}

bool asked[1001];
bool tryIntern(int u) {                      // find u a project, moving others if needed
    for (int p : likes[u])
        if (!asked[p]) {
            asked[p] = true;                     // ask each project once per search
            if (owner[p] == 0 || tryIntern(owner[p])) {
                owner[p] = u;
                return true;
            }
        }
    return false;
}

int main() {
    mt19937 rng(59);
    for (int t = 1; t <= 500; t++) {
        L = rng() % 6 + 1, R = rng() % 6 + 1, k = rng() % 15;
        for (int u = 1; u <= L; u++) likes[u].clear();
        for (int i = 0; i < k; i++) likes[rng() % L + 1].push_back(rng() % R + 1);
        best = 0;
        go(1, 0);
        fill(owner, owner + R + 1, 0);
        int pairs = 0;
        for (int u = 1; u <= L; u++) {
            fill(asked, asked + R + 1, false);
            if (tryIntern(u)) pairs++;
        }
        if (pairs != best) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem G2 · Mop the Spills

(Written for this course.)

An n × m floor; * is a spill. One mop cleans a whole row or a whole column. Print the fewest mops and which rows and columns.

4 5
..*..
..***
....*
..*.*

The obvious attempt: mop the fullest line (WA)

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

int n, m;
vector<string> grid;

int main() {
    cin >> n >> m;
    grid.resize(n);
    for (auto &row : grid) cin >> row;
    int mops = 0;
    while (true) {
        int best = 0, isRow = 0, idx = 0;          // the line with the most spills
        for (int r = 0; r < n; r++) {
            int c = count(grid[r].begin(), grid[r].end(), '*');
            if (c > best) best = c, isRow = 1, idx = r;
        }
        for (int c = 0; c < m; c++) {
            int cnt = 0;
            for (int r = 0; r < n; r++) cnt += grid[r][c] == '*';
            if (cnt > best) best = cnt, isRow = 0, idx = c;
        }
        if (best == 0) break;
        for (int i = 0; i < (isRow ? m : n); i++)
            (isRow ? grid[idx][i] : grid[i][idx]) = '.';   // mop it
        mops++;
        cout << (isRow ? "row " : "column ") << idx + 1 << "\n";
    }
    cout << "mops " << mops << "\n";
}
row 2
row 4
row 1
row 3
mops 4

Three mops are enough: row 2, column 3, column 5.

Rows and columns as a bipartite graph

  • Left side: rows. Right side: columns. A spill at (r, c) is an edge r — c.
  • A mop on row r cleans every edge at r. Cleaning every spill = choosing vertices that touch every edge = a vertex cover. We want the minimum.
  • Any matching needs a different mop for each of its edges (no mop touches two of them), so cover ≥ matching always.
  • König's theorem: in a bipartite graph the minimum cover equals the maximum matching.

Building the cover (and why it works)

  1. Find a maximum matching (Kuhn, rows on the left).
  2. From every unmatched row, walk alternately: row → any column it touches → that column's matched row → …; mark every row and column visited (call them Z).
  3. Cover K = (rows not in Z) ∪ (columns in Z).

K covers every edge. Take a spill r — c. If r is not in Z, row r is in K. If r is in Z, the walk from r reaches c (every edge from a visited row is followed), so c is in Z and in K.

|K| = matching size. Every visited column is matched (otherwise the walk found an augmenting path, impossible for a maximum matching), and its matched row is visited, so it is not in K. Every unvisited row is matched (all unmatched rows start the walk), and its matched column is not visited (columns are only entered from visited rows, and a matched column's row would then be visited). So K takes exactly one end of every matching edge and nothing else.

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

int n, m, matchCol[1001], matchRow[1001];      // matched row of a column, column of a row
vector<int> adj[1001];                         // adj[r] = columns with a spill in row r
bool used[1001];

bool tryRow(int r) {
    for (int c : adj[r])
        if (!used[c]) {
            used[c] = true;
            if (!matchCol[c] || tryRow(matchCol[c])) {
                matchCol[c] = r;
                matchRow[r] = c;
                return true;
            }
        }
    return false;
}

bool visR[1001], visC[1001];
void mark(int r) {                           // alternate: any edge, then the matched edge
    visR[r] = true;
    for (int c : adj[r])
        if (!visC[c]) {
            visC[c] = true;
            if (matchCol[c]) mark(matchCol[c]);
        }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int r = 1; r <= n; r++) {
        string s;
        cin >> s;
        for (int c = 1; c <= m; c++) if (s[c - 1] == '*') adj[r].push_back(c);   // spill = edge
    }
    int mops = 0;
    for (int r = 1; r <= n; r++) {
        fill(used, used + m + 1, false);
        if (tryRow(r)) mops++;
    }
    for (int r = 1; r <= n; r++) if (!matchRow[r]) mark(r);   // start from unmatched rows
    cout << "mops " << mops << "\nrows:";
    for (int r = 1; r <= n; r++) if (!visR[r]) cout << " " << r;
    cout << "\ncolumns:";
    for (int c = 1; c <= m; c++) if (visC[c]) cout << " " << c;
    cout << "\n";
}
mops 3
rows: 2
columns: 3 5

A clean floor:

mops 0
rows:
columns:

Complexity vs the constraints

Method Time Verdict at L, R ≤ 1000, k ≤ 10^5
first free project O(k) Wrong Answer
try every assignment exponential TLE
Kuhn O(L · k) ≤ 10^8 accepted
Hopcroft-Karp O(k √(L + R)) for 10^5 per side
Dinic on the unit network (homework 3) O(k √(L + R)) for 10^5 per side
König cover after the matching + O(L + R + k) accepted

Kuhn's worst case is rarely reached on random data; a common speed-up is to shuffle the interns, or to first match greedily and then run the searches.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
greedy first free project 3 (expected 4) no undo augmenting paths
trying every assignment Time Limit Exceeded exponential Kuhn
no asked[] mark Runtime Error (SIGSEGV) endless recursion mark each project once per search
asked[] not cleared per intern too few pairs projects never retried fill before each search
mop the fullest line mops 4 (expected 3) greedy cover König
cover = visited rows + unvisited columns wrong lines, too many sides swapped unvisited rows + visited columns
storing the graph as an n × m matrix for big n Memory Limit Exceeded n · m cells adjacency lists
applying König to a non-bipartite graph wrong answers the theorem needs two sides it only holds for bipartite graphs

Mini project

Write a BipartiteMatcher with addEdge(u, v), maxMatching() (Kuhn, with a randomised order), pairs(), minVertexCover() (König) and maxIndependentSet() (the complement of the cover). Verify on random graphs that |cover| == |matching|, that the cover touches every edge, and that the independent set has no edge inside it.

Practice

These are the four homework problems from the episode. Every answer below came from a compiled C++ program (g++ -O2 -std=c++17).

1. The largest independent set (a group with no "would accept" line inside it). Input as in G1.

Solution

The complement of a vertex cover is an independent set and vice versa, so the maximum independent set has size (L + R) − (minimum cover) = (L + R) − (maximum matching). Sample: 8 − 4.

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

int L, R, k, owner[1001];
vector<int> likes[1001];
bool asked[1001];

bool tryIntern(int u) {
    for (int p : likes[u])
        if (!asked[p]) {
            asked[p] = true;
            if (owner[p] == 0 || tryIntern(owner[p])) {
                owner[p] = u;
                return true;
            }
        }
    return false;
}
int matching() {
    int pairs = 0;
    for (int u = 1; u <= L; u++) {
        fill(asked, asked + R + 1, false);
        if (tryIntern(u)) pairs++;
    }
    return pairs;
}

int main() {
    // largest group of people with no "would accept" line inside it (independent set)
    cin >> L >> R >> k;
    for (int i = 0; i < k; i++) {
        int u, p;
        cin >> u >> p;
        likes[u].push_back(p);
    }
    // complement of a minimum vertex cover; by König its size is (L + R) - matching
    cout << L + R - matching() << "\n";
}
4

2. The most rooks on a board with holes that don't attack each other (# = hole; rooks attack along rows and columns, holes don't block).

Solution

At most one rook per row and per column: a free cell (r, c) is an edge r — c, and a placement is a matching.

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

int L, R, k, owner[1001];
vector<int> likes[1001];
bool asked[1001];

bool tryIntern(int u) {
    for (int p : likes[u])
        if (!asked[p]) {
            asked[p] = true;
            if (owner[p] == 0 || tryIntern(owner[p])) {
                owner[p] = u;
                return true;
            }
        }
    return false;
}
int matching() {
    int pairs = 0;
    for (int u = 1; u <= L; u++) {
        fill(asked, asked + R + 1, false);
        if (tryIntern(u)) pairs++;
    }
    return pairs;
}

int main() {
    // n x m board, '#' = hole. Rooks attack along rows and columns: one per row and per column.
    int n, m;
    cin >> n >> m;
    L = n, R = m;
    for (int r = 1; r <= n; r++) {
        string s;
        cin >> s;
        for (int c = 1; c <= m; c++) if (s[c - 1] == '.') likes[r].push_back(c);   // a free cell = row r with column c
    }
    cout << matching() << "\n";
}
3

3. G1 with Dinic from episode 58.

Solution

Source → each intern (capacity 1), intern → project (1), each project → sink (1). The max flow is the matching; on this unit network Dinic is O(E √V).

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

struct Edge { int to; ll cap; };
vector<Edge> e;
vector<int> g[2005];
int lvl[2005], it[2005], V;

void addEdge(int a, int b, ll c) {
    g[a].push_back(e.size());
    e.push_back({b, c});
    g[b].push_back(e.size());
    e.push_back({a, 0});
}
bool bfs(int s, int t) {
    fill(lvl, lvl + V, -1);
    lvl[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int id : g[v])
            if (e[id].cap > 0 && lvl[e[id].to] < 0) lvl[e[id].to] = lvl[v] + 1, q.push(e[id].to);
    }
    return lvl[t] >= 0;
}
ll dfs(int v, int t, ll f) {
    if (v == t) return f;
    for (int &i = it[v]; i < (int)g[v].size(); i++) {
        int id = g[v][i], u = e[id].to;
        if (e[id].cap > 0 && lvl[u] == lvl[v] + 1)
            if (ll d = dfs(u, t, min(f, e[id].cap))) {
                e[id].cap -= d;
                e[id ^ 1].cap += d;
                return d;
            }
    }
    return 0;
}

int main() {
    int L, R, k;
    cin >> L >> R >> k;
    int S = 0, T = L + R + 1;
    V = T + 1;
    for (int u = 1; u <= L; u++) addEdge(S, u, 1);           // each intern once
    for (int p = 1; p <= R; p++) addEdge(L + p, T, 1);       // each project once
    for (int i = 0; i < k; i++) {
        int u, p;
        cin >> u >> p;
        addEdge(u, L + p, 1);
    }
    ll flow = 0;
    while (bfs(S, T)) {
        fill(it, it + V, 0);
        while (ll d = dfs(S, T, LLONG_MAX)) flow += d;
    }
    cout << flow << "\n";                                    // O(E sqrt(V)) on this unit network
}
4

4. Is there a matching that places every intern? If not, prove it (Hall's condition).

Solution

Hall's theorem: every left vertex can be matched exactly when every set S of left vertices has at least |S| neighbours. If Kuhn leaves intern u unmatched, the alternating walk from u visits a set S of interns whose neighbourhood N(S) is exactly the visited projects, all matched to interns in S other than u: |N(S)| = |S| − 1. Sample: interns 1, 2, 3 only accept projects 1 and 2.

4 4 6
1 1
2 1
2 2
3 1
3 2
4 3
#include <bits/stdc++.h>
using namespace std;

int L, R, k, owner[1001];
vector<int> likes[1001];
bool asked[1001];

bool tryIntern(int u) {
    for (int p : likes[u])
        if (!asked[p]) {
            asked[p] = true;
            if (owner[p] == 0 || tryIntern(owner[p])) {
                owner[p] = u;
                return true;
            }
        }
    return false;
}
int matching() {
    int pairs = 0;
    for (int u = 1; u <= L; u++) {
        fill(asked, asked + R + 1, false);
        if (tryIntern(u)) pairs++;
    }
    return pairs;
}

bool visL[1001], visR[1001];
void reach(int u) {                    // alternating walk: any line from u, then the matched line back
    visL[u] = true;
    for (int p : likes[u])
        if (!visR[p]) {
            visR[p] = true;
            if (owner[p]) reach(owner[p]);
        }
}

int main() {
    cin >> L >> R >> k;
    for (int i = 0; i < k; i++) {
        int u, p;
        cin >> u >> p;
        likes[u].push_back(p);
    }
    if (matching() == L) { cout << "YES\n"; return 0; }
    vector<bool> matched(L + 1);
    for (int p = 1; p <= R; p++) if (owner[p]) matched[owner[p]] = true;
    int u = 1;
    while (matched[u]) u++;
    reach(u);                            // Hall violator: S = visited interns, N(S) = visited projects
    cout << "NO\nS:";
    for (int i = 1; i <= L; i++) if (visL[i]) cout << " " << i;
    cout << "\nN(S):";
    for (int p = 1; p <= R; p++) if (visR[p]) cout << " " << p;
    cout << "\n";
}
NO
S: 1 2 3
N(S): 1 2

Quick quiz

Spills on the four corners and the centre of a 3 × 3 floor. Fewest mops?

*.*
.*.
*.*

A) 2 · B) 3 · C) 4 · D) 5

Answer

B. Rows 1 and 3 clean the corners, and row 2 (or column 2) the centre. Row 1–column 1, row 2–column 2, row 3–column 3 is a matching of size 3, so 2 mops can never be enough.

Interview questions

  1. What is a bipartite graph? How do you test for one? Two sides, edges only across; equivalently no odd cycle. Test with a BFS 2-colouring.
  2. What is an augmenting path and why does it matter? An alternating path between two free vertices; flipping it grows the matching by 1, and a matching is maximum exactly when none exists (Berge).
  3. Describe Kuhn's algorithm and its complexity. For each left vertex, DFS for an augmenting path with a visited mark on right vertices; O(V · E).
  4. When would you use Hopcroft-Karp? For large graphs (10^5 vertices): it finds many shortest augmenting paths per phase, O(E √V).
  5. State König's theorem. In a bipartite graph, the size of a minimum vertex cover equals the size of a maximum matching.
  6. How is matching related to flow? Source → left (1), left → right (1), right → sink (1); max flow = max matching.
  7. What is Hall's theorem? A bipartite graph has a matching saturating the left side iff |N(S)| ≥ |S| for every subset S of the left side.

Glossary

Term Meaning Example
Bipartite graph Two sides, edges only between them interns and projects
Left / right side The two groups rows / columns
Matching Edges with no shared endpoint 1–2, 2–1, 3–3, 4–4
Maximum matching The largest matching 4
Perfect matching Every vertex matched G1 sample
Free (unmatched) vertex A vertex not in the matching intern 2 after the greedy
Alternating path Edges alternately outside / inside the matching 2–1=1–2=3–3=4–4
Augmenting path An alternating path between two free vertices flips to +1 pair
Berge's theorem Maximum ⇔ no augmenting path why Kuhn is correct
Kuhn's algorithm One augmenting-path DFS per left vertex O(L · k)
owner[p] The intern on project p (0 = free) owner[1] = 2
asked[p] Project p already examined in this search stops endless recursion
Stack overflow Recursion deeper than the stack Runtime Error (SIGSEGV)
Segmentation fault (SIGSEGV) The program touched memory it may not the missing mark
Vertex cover Vertices touching every edge row 2, columns 3, 5
Minimum vertex cover The smallest cover 3 mops
König's theorem Bipartite: min cover = max matching G2
Independent set Vertices with no edge between them homework 1
Hall's theorem Left side matchable ⇔ |N(S)| ≥ |S| homework 4
N(S) The neighbours of a set S projects of interns 1–3
Hopcroft-Karp Matching with shortest augmenting paths in phases O(E √V)
Exponential time Time that multiplies with every extra element try every assignment
Stress test Comparing a fast solution with a slow, surely-correct one on many random inputs all 500 tests passed
Wrong Answer (WA) A wrong output 3, mops 4
Min-cost max-flow The cheapest among the maximum flows next episode

Summary

  • A matching pairs vertices of two sides with no shared ends; greedy pairing is wrong (3 vs 4).
  • An augmenting path from a free left vertex to a free right vertex adds one pair when flipped.
  • Kuhn: one DFS per left vertex, asked[] once per search (cleared each time), O(L · k); without the mark: Runtime Error (SIGSEGV).
  • Any cover needs at least as many vertices as any matching has edges; König: equal in bipartite graphs.
  • Build the cover from the unmatched rows: unvisited rows + visited columns (mops 3, row 2, columns 3 5).

Solutions in C++, Java and Python

Problem G1 · Interns and Projects

C++

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

int L, R, k, owner[1001];                      // owner[p] = intern on project p (0 = free)
vector<int> likes[1001];
bool asked[1001];
bool tryIntern(int u) {                      // find u a project, moving others if needed
    for (int p : likes[u])
        if (!asked[p]) {
            asked[p] = true;                     // ask each project once per search
            if (owner[p] == 0 || tryIntern(owner[p])) {
                owner[p] = u;
                return true;
            }
        }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> L >> R >> k;
    for (int i = 0; i < k; i++) {
        int u, p;
        cin >> u >> p;
        likes[u].push_back(p);
    }
    int pairs = 0;
    for (int u = 1; u <= L; u++) {
        fill(asked, asked + R + 1, false);
        if (tryIntern(u)) pairs++;
    }
    cout << pairs << "\n";
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static int L, R;
    static int[] owner;                        // owner[p] = intern on project p (0 = free)
    static boolean[] asked;
    static List<Integer>[] likes;

    static boolean tryIntern(int u) {          // find u a project, moving others if needed
        for (int p : likes[u])
            if (!asked[p]) {
                asked[p] = true;
                if (owner[p] == 0 || tryIntern(owner[p])) { owner[p] = u; return true; }
            }
        return false;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(br.readLine());
        L = Integer.parseInt(tk.nextToken()); R = Integer.parseInt(tk.nextToken());
        int k = Integer.parseInt(tk.nextToken());
        likes = new List[L + 1];
        for (int u = 1; u <= L; u++) likes[u] = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            tk = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(tk.nextToken()), p = Integer.parseInt(tk.nextToken());
            likes[u].add(p);
        }
        owner = new int[R + 1];
        asked = new boolean[R + 1];
        int pairs = 0;
        for (int u = 1; u <= L; u++) {
            Arrays.fill(asked, false);
            if (tryIntern(u)) pairs++;
        }
        System.out.println(pairs);
    }
}
4

Python

import sys
sys.setrecursionlimit(10000)

def main():
    data = sys.stdin.read().split()
    L, R, k = int(data[0]), int(data[1]), int(data[2])
    likes = [[] for _ in range(L + 1)]
    for i in range(k):
        likes[int(data[3 + 2 * i])].append(int(data[4 + 2 * i]))
    owner = [0] * (R + 1)                     # owner[p] = intern on project p (0 = free)

    def try_intern(u, asked):
        for p in likes[u]:
            if not asked[p]:
                asked[p] = True
                if owner[p] == 0 or try_intern(owner[p], asked):
                    owner[p] = u
                    return True
        return False

    pairs = sum(1 for u in range(1, L + 1) if try_intern(u, [False] * (R + 1)))
    print(pairs)

main()
4

Problem G2 · Mop the Spills

C++

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

int n, m, matchCol[1001], matchRow[1001];      // matched row of a column, column of a row
vector<int> adj[1001];                         // adj[r] = columns with a spill in row r
bool used[1001];

bool tryRow(int r) {
    for (int c : adj[r])
        if (!used[c]) {
            used[c] = true;
            if (!matchCol[c] || tryRow(matchCol[c])) {
                matchCol[c] = r;
                matchRow[r] = c;
                return true;
            }
        }
    return false;
}

bool visR[1001], visC[1001];
void mark(int r) {                           // alternate: any edge, then the matched edge
    visR[r] = true;
    for (int c : adj[r])
        if (!visC[c]) {
            visC[c] = true;
            if (matchCol[c]) mark(matchCol[c]);
        }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int r = 1; r <= n; r++) {
        string s;
        cin >> s;
        for (int c = 1; c <= m; c++) if (s[c - 1] == '*') adj[r].push_back(c);   // spill = edge
    }
    int mops = 0;
    for (int r = 1; r <= n; r++) {
        fill(used, used + m + 1, false);
        if (tryRow(r)) mops++;
    }
    for (int r = 1; r <= n; r++) if (!matchRow[r]) mark(r);   // start from unmatched rows
    cout << "mops " << mops << "\nrows:";
    for (int r = 1; r <= n; r++) if (!visR[r]) cout << " " << r;
    cout << "\ncolumns:";
    for (int c = 1; c <= m; c++) if (visC[c]) cout << " " << c;
    cout << "\n";
}

Java

import java.util.*;

public class Main {
    static int n, m;
    static int[] matchCol, matchRow;
    static boolean[] used, visR, visC;
    static List<Integer>[] adj;

    static boolean tryRow(int r) {
        for (int c : adj[r])
            if (!used[c]) {
                used[c] = true;
                if (matchCol[c] == 0 || tryRow(matchCol[c])) { matchCol[c] = r; matchRow[r] = c; return true; }
            }
        return false;
    }
    static void mark(int r) {                 // any edge from a row, the matched edge back from a column
        visR[r] = true;
        for (int c : adj[r])
            if (!visC[c]) { visC[c] = true; if (matchCol[c] != 0) mark(matchCol[c]); }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt(); m = sc.nextInt();
        adj = new List[n + 1];
        for (int r = 1; r <= n; r++) {
            adj[r] = new ArrayList<>();
            String s = sc.next();
            for (int c = 1; c <= m; c++) if (s.charAt(c - 1) == '*') adj[r].add(c);
        }
        matchCol = new int[m + 1]; matchRow = new int[n + 1];
        used = new boolean[m + 1]; visR = new boolean[n + 1]; visC = new boolean[m + 1];
        int mops = 0;
        for (int r = 1; r <= n; r++) { Arrays.fill(used, false); if (tryRow(r)) mops++; }
        for (int r = 1; r <= n; r++) if (matchRow[r] == 0) mark(r);
        StringBuilder sb = new StringBuilder("mops " + mops + "\nrows:");
        for (int r = 1; r <= n; r++) if (!visR[r]) sb.append(" ").append(r);
        sb.append("\ncolumns:");
        for (int c = 1; c <= m; c++) if (visC[c]) sb.append(" ").append(c);
        System.out.println(sb);
    }
}
mops 3
rows: 2
columns: 3 5

Python

import sys
sys.setrecursionlimit(10000)

def main():
    data = sys.stdin.read().split()
    n, m = int(data[0]), int(data[1])
    adj = [[]] + [[c + 1 for c, ch in enumerate(data[2 + r]) if ch == "*"] for r in range(n)]
    match_col, match_row = [0] * (m + 1), [0] * (n + 1)

    def try_row(r, used):
        for c in adj[r]:
            if not used[c]:
                used[c] = True
                if match_col[c] == 0 or try_row(match_col[c], used):
                    match_col[c], match_row[r] = r, c
                    return True
        return False

    mops = sum(1 for r in range(1, n + 1) if try_row(r, [False] * (m + 1)))
    vis_r, vis_c = [False] * (n + 1), [False] * (m + 1)

    def mark(r):                              # any edge, then the matched edge back
        vis_r[r] = True
        for c in adj[r]:
            if not vis_c[c]:
                vis_c[c] = True
                if match_col[c]:
                    mark(match_col[c])

    for r in range(1, n + 1):
        if not match_row[r]:
            mark(r)
    print("mops", mops)
    print("rows:" + "".join(f" {r}" for r in range(1, n + 1) if not vis_r[r]))
    print("columns:" + "".join(f" {c}" for c in range(1, m + 1) if vis_c[c]))

main()
mops 3
rows: 2
columns: 3 5