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)
- Find a maximum matching (Kuhn, rows on the left).
- 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).
- 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
- 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.
- 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).
- 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).
- When would you use Hopcroft-Karp? For large graphs (10^5 vertices): it finds many shortest augmenting paths per phase, O(E √V).
- State König's theorem. In a bipartite graph, the size of a minimum vertex cover equals the size of a maximum matching.
- How is matching related to flow? Source → left (1), left → right (1), right → sink (1); max flow = max matching.
- 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 (
3vs4). - 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