On this page

Bipartite Graphs, Matching & the Hungarian Algorithm

Why this exists

A huge class of allocation problems has the same shape: two kinds of things, a compatibility relation between them, and the requirement that each thing is used at most once. Workers and jobs. Students and project slots. Taxis and riders. Exams and time slots. Doctors and residency programmes. Rows and columns of a grid. Draw one vertex per thing and one edge per compatible pair and you get a bipartite graph: the vertices split into two sides and every edge crosses from one side to the other. A matching is a set of edges with no shared endpoint — a valid allocation — and the question is almost always "how large can it be?" or "how cheap can a complete one be?".

Brute force is hopeless: a complete bipartite graph with 20 vertices per side has perfect matchings. The theory that makes the problem easy is old and beautiful. Dénes König proved in 1931 that in a bipartite graph the maximum matching equals the minimum vertex cover; Jenő Egerváry generalised it to weights the same year; Philip Hall characterised when a perfect matching exists in 1935; Claude Berge proved in 1957 that a matching is maximum exactly when there is no augmenting path. Harold Kuhn turned König's and Egerváry's work into the Hungarian method for the assignment problem in 1955 (naming it after them), James Munkres showed it runs in polynomial time in 1957, John Hopcroft and Richard Karp made unweighted matching run in in 1973, and David Gale and Lloyd Shapley solved the stable version in 1962 — work that, through Alvin Roth's redesign of the US medical residency match, earned Roth and Shapley the 2012 Nobel Memorial Prize in Economics.

Matching is also the bridge to the next lesson. Bipartite matching is a maximum-flow problem with unit capacities, and every idea here — augmenting paths, residual structure, a min-cut certificate of optimality, potentials that keep reduced costs non-negative — reappears in network flow in general form. Learn it here on the clean special case, and flow will feel like a generalisation rather than a new subject.

Pattern triggers

If the problem says or has…Think of…
"Split into two groups so that no two in the same group conflict", "two-colour"Bipartite check (BFS/DFS two-colouring)
"Each X can be paired with some Ys; each used at most once; maximise pairs"Maximum bipartite matching (Kuhn, Hopcroft–Karp)
up to , up to , matching requiredHopcroft–Karp () or Dinic on the unit network
"Minimum number of rows/columns to cover all marked cells", "remove all coins with fewest line moves"König: min vertex cover = max matching
"Largest set of cells/people with no conflicting pair", conflicts form a grid/parity structureMax independent set = − max matching (bipartite only)
"Minimum number of chains/paths to cover a DAG", "fewest taxis/workers to serve timed jobs"Min path cover = − max matching on the split graph
"Does a perfect assignment exist?", "every subset of k people likes at least k jobs"Hall's theorem
" workers, jobs, cost matrix, minimise total cost", Assignment problem: Hungarian algorithm
and a cost matrixBitmask DP is also fine — and often easier
"Preferences / rankings on both sides, no pair would rather defect"Stable matching: Gale–Shapley
"Maximise matched pairs, but some edges have weights / capacities > 1"Generalise to flow / min-cost flow
Pairing within one set (roommates, general graph), odd cycles possibleNot bipartite: Edmonds' blossom algorithm (mentioned under Variations)

The meta-trigger: two sides, compatibility edges, each vertex used at most once. If you can name the two sides, you are in this lesson. If the "two sides" are really one set paired with itself, you are not, and the bipartite theorems below fail.

Intuition & first principles

Bipartite means "no odd cycle"

A graph is bipartite if can be partitioned into and with every edge having one end in each. Equivalently, it is 2-colourable: colour white and black and every edge joins different colours.

Walk along any cycle in a bipartite graph: each step switches sides, and to return to the start you must switch an even number of times. So a bipartite graph has no odd cycle. The surprise is the converse — no odd cycle is also sufficient.

Theorem (König, 1936). A graph is bipartite if and only if it contains no cycle of odd length.

Proof of the converse. Work on one connected component; components are independent. Pick a root and run BFS, getting distances . Colour white if is even and black if odd. Suppose some edge has both ends the same colour, so . Take BFS-tree paths from to and from to , and let be the last vertex they share. The cycle (along ), (the edge), (back along ) has length , which is odd because is even. That contradicts "no odd cycle", so the colouring is proper.

The proof is also the algorithm: BFS-colour by parity; the first edge inside one colour class is an odd cycle certificate, and you can print it by walking both endpoints up the BFS tree to their meeting point. Two-colouring costs . The Graphs overview has the minimal version; the code below returns a certificate either way.

Matchings and augmenting paths

Fix a matching . A vertex is matched if an edge of touches it and free otherwise. An alternating path alternates between edges not in and edges in . An augmenting path is an alternating path whose two endpoints are both free.

An augmenting path starts and ends with non-matching edges, so it has one more non-matching edge than matching edges. Flip it — take the symmetric difference — and every interior vertex stays matched (to a different partner), the two free endpoints become matched, and the matching grows by exactly one. That is the entire engine of unweighted matching: find an augmenting path, flip it, repeat.

The analogy is musical chairs played cooperatively. A newcomer wants chair , which is occupied by ; is happy to move if it can find another chair, perhaps by displacing , and so on until someone reaches an empty chair. The chain of displacements is an augmenting path. The precise statement of why this suffices is Berge's theorem.

Theorem (Berge, 1957). A matching in any graph (bipartite or not) is maximum if and only if there is no augmenting path with respect to .

Proof. () If an augmenting path existed, flipping it would give a larger matching, so was not maximum.

() Suppose is not maximum; let be a maximum matching, . Consider , the edges in exactly one of the two. Every vertex has at most one -edge and at most one -edge, so every vertex has degree in , and is a disjoint union of paths and cycles whose edges alternate between and . An alternating cycle has equally many edges of each. Since has more -edges than -edges in total, some path component has more -edges than -edges — it starts and ends with -edges. Its endpoints are not covered by (otherwise the path would continue along that -edge), so it is an -augmenting path.

The proof gives more than the theorem: contains at least vertex-disjoint augmenting paths. Hopcroft–Karp's complexity bound rests on exactly that remark.

Berge's theorem holds in general graphs, but finding an augmenting path is easy only in bipartite graphs. In a bipartite graph, an alternating path from a free left vertex always uses non-matching edges left-to-right and matching edges right-to-left, so a plain DFS or BFS over that directed view finds one. In general graphs, odd cycles (blossoms) can make a DFS miss an augmenting path; Edmonds' 1965 blossom algorithm handles that and is out of scope here.

Mechanics

The picture

flowchart LR
    subgraph Left["Left side L"]
        L0["L0"]
        L1["L1"]
        L2["L2"]
        L3["L3"]
    end
    subgraph Right["Right side R"]
        R0["R0"]
        R1["R1"]
        R2["R2"]
        R3["R3"]
    end
    L0 --- R0
    L0 --- R1
    L1 --- R0
    L1 --- R3
    L2 --- R2
    L3 --- R1

This is the graph of the trace below: adj = [[0, 1], [0, 3], [2], [1]] (left vertex u lists its right neighbours, in the order they are tried). The interesting vertex is L3: its only neighbour R1 will already be taken when it arrives, so it must evict someone.

Kuhn's algorithm

Kuhn's algorithm (the name used in competitive programming for the augmenting-path method applied to bipartite graphs) runs one DFS per left vertex. try_kuhn(u) scans u's neighbours; for each right vertex v not yet visited in this search, it marks v and succeeds if v is free or if v's current partner can be re-matched recursively. On success, v is (re)assigned to u on the way back up the recursion, which flips the augmenting path in place.

flowchart TD
    A["try_kuhn(u)"] --> B{"next neighbour v of u?"}
    B -->|"none left"| F["return False"]
    B -->|"v already seen"| B
    B -->|"v unseen"| C["mark v seen"]
    C --> D{"v free?"}
    D -->|"yes"| G["match_r[v] = u, return True"]
    D -->|"no, owned by w"| E{"try_kuhn(w)?"}
    E -->|"True"| G
    E -->|"False"| B

Two details matter. The seen array is over right vertices and is reset for each new root: within one search, a right vertex that failed once will fail again, so revisiting it would only waste time (and could loop). And the outer loop needs to try each left vertex only once: if try_kuhn(u) fails, u can never be matched later either. (Proof: if no augmenting path starts at free now, later augmentations never create one — a lemma proved under Correctness and on cp-algorithms' Kuhn page.)

Trace: Kuhn on the 4 + 4 graph

Computed by running the algorithm (the same generator as the visualiser above). match_r[v] is the left partner of right vertex v.

#Search fromDFS stepsAugmenting path flippedmatch_r after (R0, R1, R2, R3)Size
1L0L0→R0: freeL0–R0L0, –, –, –1
2L1L1→R0: owned by L0, recurse; L0→R0: seen, skip; L0→R1: freeL1–R0–L0–R1L1, L0, –, –2
3L2L2→R2: freeL2–R2L1, L0, L2, –3
4L3L3→R1: owned by L0, recurse; L0→R0: owned by L1, recurse; L1→R0: seen; L1→R3: freeL3–R1–L0–R0–L1–R3L0, L3, L2, L14

Row 4 is the point of the algorithm. L3 takes R1 from L0; L0 takes R0 from L1; L1 finds the free R3. Three matched pairs change partner and the matching grows by one. A greedy algorithm that never revisits a decision would have stopped at size 3.

Hopcroft–Karp: many shortest augmenting paths per phase

Kuhn finds one augmenting path per DFS, possibly a long one, and that costs searches of each. Hopcroft–Karp works in phases. Each phase:

  1. BFS from all free left vertices simultaneously, alternating non-matching edges (left → right) and matching edges (right → left), computing a layer number dist[u] for each left vertex. Stop at the first layer from which a free right vertex is reachable; call the length of those shortest augmenting paths .
  2. DFS from each free left vertex, moving only from layer to layer , to find a maximal set of vertex-disjoint shortest augmenting paths — not maximum, just "no more can be added without sharing a vertex". Flip them all.

A failed DFS marks its vertex dead (dist[u] = INF) so no later DFS in the phase re-explores it, and a per-vertex edge pointer (the "current arc", the same trick Dinic uses in flow) ensures each edge is scanned times per phase. A phase is therefore .

flowchart LR
    S["free left vertices<br/>layer 0"] -->|"non-matching edges"| A["right vertices"]
    A -->|"matching edges"| B["left vertices<br/>layer 1"]
    B -->|"non-matching edges"| C["right vertices"]
    C -->|"matching edges"| D["left vertices<br/>layer 2"]
    D -->|"non-matching edges"| T["a free right vertex<br/>ends a shortest augmenting path"]

Why only phases? Two facts, proved under Correctness:

  • Shortest augmenting path length strictly increases from one phase to the next (because each phase destroys every augmenting path of the current shortest length).
  • Counting argument. After phases, every augmenting path has length greater than . By the remark after Berge's theorem, contains vertex-disjoint augmenting paths, each using more than vertices, so . Each further phase adds at least one edge, so at most more phases remain.

Total: at most phases of each, i.e. . On the 4 + 4 graph above Hopcroft–Karp finishes in a single phase (the greedy DFS from L1 grabs R3 directly), which shows a real effect: the order in which you explore matters for Kuhn's running time, while Hopcroft–Karp's bound does not depend on it.

König's theorem and a constructive vertex cover

A vertex cover is a set of vertices touching every edge. Every edge of a matching needs its own cover vertex (matching edges share no endpoints), so for any graph for every matching and cover — weak duality. In bipartite graphs the bound is tight.

Theorem (König, 1931; Egerváry, 1931). In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

The proof (in Correctness) is a construction you will implement: take a maximum matching, let be all vertices reachable from free left vertices by alternating paths, and output

Example: adj = [[0, 1], [0], [0, 2, 3], [0]] (L0–{R0, R1}, L1–{R0}, L2–{R0, R2, R3}, L3–{R0}). Hopcroft–Karp finds the maximum matching L0–R1, L1–R0, L2–R2 (size 3); L3 is free because its only neighbour R0 is held by L1, which has nowhere else to go.

flowchart LR
    L3["L3 (free, in Z)"] -->|"non-matching"| R0["R0 (in Z, COVER)"]
    R0 -->|"matching"| L1["L1 (in Z)"]
    L0["L0 (not in Z, COVER)"] -->|"matched"| R1["R1"]
    L2["L2 (not in Z, COVER)"] -->|"matched"| R2["R2"]
    L2 --- R3["R3"]
    L0 --- R0
    L2 --- R0

Alternating search from L3: L3 → R0 (non-matching), R0 → L1 (matching), and L1 has no other edges. So and — three vertices, equal to the matching size, and you can check every one of the 7 edges touches L0, L2 or R0.

Hall's marriage theorem

For let be the set of right vertices adjacent to some vertex of . If for some , the vertices in cannot all be matched — there are too few partners to go round. Hall's theorem says this is the only obstruction.

Theorem (Hall, 1935). A bipartite graph has a matching that saturates if and only if for every .

The proof via König is three lines (see Correctness), and it is constructive: when no -saturating matching exists, the set from the König construction is a Hall violator with . In the example, and : two vertices, one possible partner. Algorithms that must explain why an assignment is impossible ("these 7 shifts can only be covered by these 5 nurses") output exactly this set.

A useful corollary: every -regular bipartite graph () has a perfect matching, and by removing it and repeating, its edges split into perfect matchings. This is how Birkhoff–von Neumann decompositions and many scheduling "rounds" constructions work.

Maximum independent set, minimum edge cover

An independent set has no two adjacent vertices. is independent exactly when is a vertex cover (an edge inside would be uncovered by the complement, and vice versa). So in any graph, where is the max independent set size and the min vertex cover size (Gallai, 1959). In a bipartite graph König gives (the matching number), hence

and the independent set itself is the complement of the König cover. In the example, , size ; no edge joins two of them, because every edge touches L0, L2 or R0.

For general graphs, maximum independent set is NP-hard; bipartiteness is what makes it polynomial. This is why "seat as many students as possible with no two able to see each other" is solvable for the seating patterns where conflicts only join adjacent columns (column parity is a 2-colouring).

Gallai's other identity: with no isolated vertices, the minimum edge cover (edges touching every vertex) has size , in any graph. Build it from a maximum matching plus one arbitrary edge per unmatched vertex.

Minimum path cover in a DAG

Given a DAG, cover all vertices with the fewest vertex-disjoint paths. Build the split graph: a left copy and a right copy of every vertex, and an edge for every DAG edge . A matching in the split graph is a set of "successor" choices in which each vertex has at most one successor and at most one predecessor — precisely a set of disjoint paths. Each matched edge merges two paths into one, so

flowchart LR
    subgraph DAG["DAG"]
        a["a"] --> b["b"]
        a --> c["c"]
        b --> d["d"]
        c --> d
    end
    subgraph Split["Split graph"]
        ao["a out"] --- bi["b in"]
        ao --- ci["c in"]
        bo["b out"] --- di["d in"]
        co["c out"] --- di
    end

For this 4-vertex DAG the split graph's maximum matching has size 2: b in and c in both have a out as their only neighbour, so at most one of them is matched, and d in adds at most one more. Matching a out–b in and b out–d in gives paths: a→b→d and c on its own. If paths may share vertices, take the transitive closure first; by Dilworth's theorem, the minimum number of chains covering a partial order equals the maximum antichain, and this computation finds both. The classic application is "how many taxis are needed to serve a list of timed rides, where a taxi can do ride after ride if it can reach 's pickup in time" — rides are vertices, feasible successions are edges.

The assignment problem and the Hungarian algorithm

Now every edge has a cost. Given an cost matrix , find a permutation minimising — a minimum-cost perfect matching in the complete bipartite graph . (Maximisation: negate costs. Rectangular : the algorithm below handles it directly. Missing edges: give them a large cost and check at the end.)

The key idea is potentials, also called the dual or "labelling". Assign a number to each row and to each column with

Then for any perfect matching , . So every feasible potential is a lower bound on the optimum. If we find a perfect matching that uses only tight edges — reduced cost — its cost equals the bound and both are optimal. This is LP duality specialised to bipartite matching; Egerváry's 1931 theorem says the best lower bound always equals the optimum.

The algorithm grows the matching one row at a time. To add row , it searches for an augmenting path in the subgraph of tight edges. When the search gets stuck, it raises potentials of the rows it reached and lowers potentials of the columns it reached by the smallest reduced cost out of the reached set; this keeps all reduced costs non-negative, keeps matched edges tight, and makes at least one new edge tight, so the search can continue. Viewed differently, it is Dijkstra on reduced costs: is the next-closest unreached column. The version (Edmonds & Karp 1972, Tomizawa 1971; the compact form popularised by e-maxx/cp-algorithms) maintains minv[j], the smallest reduced cost to reach column j from the reached rows, so each Dijkstra step costs , each row costs steps, and the total is .

Worked example: Hungarian algorithm on a 4 × 4 matrix

All values below were produced by running the implementation in this lesson with logging (0-indexed rows and columns; = row potentials, = column potentials, "col → row" = current assignment).

Row addedDijkstra steps: (expanded row, , column reached, its owner) after aftercol → row after
0(r0, 2, c1, free)2, 0, 0, 00, 0, 0, 0c1→r0
1(r1, 3, c2, free)2, 3, 0, 00, 0, 0, 0c1→r0, c2→r1
2(r2, 1, c2, r1); (r1, 1, c1, r0); (r0, 2, c0, free)4, 6, 4, 00, −2, −3, 0c0→r1, c1→r0, c2→r2
3(r3, 4, c3, free)4, 6, 4, 40, −2, −3, 0c0→r1, c1→r0, c2→r2, c3→r3

Row 2 is the interesting one ( in the table is the increment of the Dijkstra distance at each step, not the cumulative distance). Its cheapest column is c2 (cost 1), but r1 holds c2. The search expands r1, whose cheapest unreached column is c1 at a further (held by r0), then expands r0, whose cheapest unreached column is the free c0 at a further . The augmenting path that gets flipped is r2→c2, r1→c0: r1 moves from c2 to c0 (cost 6) so that r2 can take c2 (cost 1). Column c1 was reached but is not on the final path — exactly like a Dijkstra node that is settled but not on the shortest path to the target.

Final assignment r0→c1, r1→c0, r2→c2, r3→c3, cost (a brute force over all 24 permutations agrees). The certificate: , and the final reduced-cost matrix is

non-negative everywhere and zero on the chosen cells (bold). Anyone can verify optimality from alone without re-running the algorithm — the same "certificate" idea as the min cut in flow.

Stable matching: Gale–Shapley

Now each side ranks the other. A perfect matching is unstable if some man and woman , not matched to each other, both prefer each other to their assigned partners — a blocking pair that would defect. A matching with no blocking pair is stable. (The traditional "men/women" vocabulary comes from the 1962 paper; in practice the sides are applicants and programmes, students and schools, and so on.)

Gale–Shapley (deferred acceptance). While some man is free, he proposes to the highest-ranked woman he has not yet proposed to. She tentatively accepts if she is free or prefers him to her current partner (who becomes free again), otherwise she rejects him. Acceptances are deferred: nothing is final until the end.

Trace on 4 + 4 people, computed by the implementation below (a FIFO queue of free men):

  • Men's preferences (best first): m0: w1 w0 w2 w3 · m1: w0 w2 w3 w1 · m2: w1 w0 w2 w3 · m3: w1 w2 w3 w0
  • Women's preferences: w0: m0 m3 m2 m1 · w1: m1 m3 m2 m0 · w2: m0 m3 m1 m2 · w3: m2 m1 m0 m3
#ProposalWoman's current partnerOutcomeEngaged pairs after
1m0 → w1–acceptsm0–w1
2m1 → w0–acceptsm0–w1, m1–w0
3m2 → w1m0 (her 4th)prefers m2 (3rd): accepts, m0 freem1–w0, m2–w1
4m3 → w1m2 (3rd)prefers m3 (2nd): accepts, m2 freem1–w0, m3–w1
5m0 → w0m1 (her 4th)prefers m0 (1st): accepts, m1 freem0–w0, m3–w1
6m2 → w0m0 (1st)rejectsm0–w0, m3–w1
7m1 → w2–acceptsm0–w0, m1–w2, m3–w1
8m2 → w2m1 (3rd)m2 is her 4th: rejectsunchanged
9m2 → w3–acceptsm0–w0, m1–w2, m2–w3, m3–w1

Result: m0–w0, m1–w2, m2–w3, m3–w1. This instance has exactly two stable matchings (checked by brute force over all 24); running the algorithm with the women proposing gives the other one, m0–w0, m1–w1, m2–w3, m3–w2. Compare them: m1 gets his 2nd choice when men propose and his 4th when women propose; w1 gets her 2nd choice when men propose and her 1st when women propose. That asymmetry is a theorem.

The ladder: brute force → better → optimal

Rung 1: try all subsets of edges —

Enumerate edge subsets, keep those with no shared endpoints, return the largest. Correct, useless beyond about 25 edges. For the assignment problem the analogue is trying all permutations — fine for or so, and the right way to test the real algorithms.

Rung 2: greedy — fast, wrong

Scan left vertices, match each to any free neighbour. , and it can be off by a factor of two: on L0–{R0, R1}, L1–{R0}, greedy matches L0–R0 and strands L1, while the maximum is 2. (On the trace graph greedy happens to be lucky: L0–R0, L1–R3, L2–R2, L3–R1.) Greedy produces a maximal matching (cannot be extended by adding an edge), and any maximal matching is at least half a maximum one — because every edge of a maximum matching must touch the maximal one. Greedy is still worth running first: it finds most of the matching instantly, and Kuhn then only searches from the leftover free vertices, which often speeds it up several times in practice.

Rung 3: Kuhn —

One DFS per left vertex, each , so , usually written . Short and robust; the right default for a few thousand or for interviews. Its weakness is long augmenting paths found one at a time.

Rung 4: Hopcroft–Karp —

Batch many shortest augmenting paths per phase. Required for ; on random graphs it typically needs only a handful of phases, far below the worst-case . Equivalent alternative: run Dinic's max-flow on the unit network , which is also (the same analysis) and is what many people keep in their library instead.

Weighted rungs: assignment

permutations → bitmask DP over the set of used columns, naively or with a row-by-popcount trick, fine to → Hungarian , fine to in the low thousands in C++ → for sparse graphs or extra constraints, min-cost flow, .

RungProblemTimeSpaceUse when
Subsets / permutationseither / testing, tiny inputs
Greedyunweightedwarm start only (≥ ½ optimal)
Kuhnunweighted few thousand, interviews
Hopcroft–Karpunweighted up to –
Bitmask DPassignment
Hungarianassignmentdense, up to low thousands (C++)
Min-cost flowweighted, capacitiessparse, side constraints
Gale–Shapleystable (ranked)preferences, no money

Correctness

Kuhn's algorithm

Each search is correct. try_kuhn(u) performs a DFS over the directed graph whose arcs are non-matching edges left → right and matching edges right → left; reaching a free right vertex means an augmenting path exists, and the reassignment on the way back flips exactly that path. Not revisiting a right vertex within one search is safe: if a DFS through v failed, every alternating continuation from v's partner has been explored, and nothing in the matching has changed since.

Each left vertex needs one try. Claim: if there is no augmenting path from free vertex with respect to , there is none with respect to for any augmenting path either. Sketch (cp-algorithms, Kuhn page): suppose has an augmenting path from . If is disjoint from , it was augmenting for . Otherwise follow from to its first vertex on ; from there, continue along in the direction that keeps the alternation (one direction does), reaching a free endpoint of — an -augmenting path from . Contradiction. So a vertex whose search fails can be discarded forever. Combined with Berge's theorem, when every left vertex has been tried, no augmenting path exists and the matching is maximum.

Hopcroft–Karp

Let be the matching after phase , the shortest augmenting path length at the start of phase .

Lemma 1. Let be the length of a shortest -augmenting path, let be vertex-disjoint -augmenting paths of length , and . If is -augmenting, then (counting edges). Proof (Hopcroft & Karp 1973; CLRS 4th ed. §25.1): is a matching with more edges than , so by the remark after Berge's theorem contains at least vertex-disjoint -augmenting paths, each of length . Hence , which rearranges to the claim.

Lemma 2. . A phase flips a maximal set of vertex-disjoint shortest augmenting paths. Let be any augmenting path afterwards. If is vertex-disjoint from , it was already an -augmenting path; it cannot have length exactly (it could then have been added to the maximal set), so . If shares a vertex with some , then is matched in by an edge of (every vertex of is matched along after the flip), and an augmenting path through a matched vertex must use its matching edge, so and Lemma 1 gives . Augmenting path lengths are odd, so in both cases .

Bound. After phases, ; the counting argument in Mechanics then leaves at most phases. Each phase is with the current-arc pointer, so the total is .

König's theorem

Let be a maximum matching, the free vertices of , and the set of vertices reachable from by alternating paths (non-matching edges , matching edges ). Set .

is a cover. Take an edge , , . If , then . If : if is non-matching, the alternating search continues to , so , . If is the matching edge of , then was reached through (a matched left vertex is only entered from its partner; and since it is matched), so , .

. Every is matched — otherwise the alternating path reaching it would be augmenting, contradicting maximality (Berge). Every is matched — all free left vertices are in . And no matching edge has both ends in : if is matched to , the search continues to , so and . So each vertex of is an endpoint of a distinct matching edge, giving ; weak duality gives .

Hall's theorem

Necessity is the counting argument. Sufficiency via König: suppose no matching saturates , so , so there is a cover with . Let . Every edge from ends in (it must be covered and its left end is not in ), so and . That violates Hall's condition.

Hungarian algorithm

Invariants maintained after every potential update (cp-algorithms, "Hungarian algorithm"; Kuhn 1955; Munkres 1957):

  1. Dual feasibility: for all . The update subtracts from reduced costs between reached rows and unreached columns, and is the minimum of exactly those, so they stay ; between reached rows and reached columns the change is ; between unreached rows and reached columns it is .
  2. Complementary slackness: every matched edge is tight. Matched edges inside the reached set keep their reduced cost (both ends change by ); a matched edge cannot connect a reached column to an unreached row, because reaching a matched column immediately reaches its row.
  3. Progress: after the update at least one new column becomes reachable via a tight edge (the one achieving ), so each row phase ends after at most updates with an augmenting path of tight edges.

When all rows are matched, the matching uses only tight edges, so its cost is , which is a lower bound on every perfect matching by dual feasibility. Hence optimal.

Gale–Shapley

Termination. Each man proposes to each woman at most once, so there are at most proposals (in fact at most ).

Perfect matching. Once a woman receives a proposal she stays engaged forever (to successively better partners). If some man ended free, he proposed to every woman, so every woman is engaged — to men among the other , impossible.

Stability. Suppose and block: each prefers the other to their final partner. Since prefers to his final partner, he proposed to earlier. She either rejected him then or dumped him later, in both cases for someone she prefers; her partners only improve, so she ends with someone she prefers to . Contradiction.

Proposer-optimality. Call valid for if some stable matching pairs them. Claim: no man is ever rejected by a valid woman; consequently each man ends with his best valid partner, and all men simultaneously get their best valid partner — the outcome does not depend on proposal order. Proof: consider the first time a man is rejected by a valid woman , in favour of whom she prefers. Since is valid for , some stable matching pairs –; let be 's partner in . When proposed to , he had not yet been rejected by any valid woman (this is the first such rejection), so he had not proposed to yet or she had not rejected him — either way he ranks above . Then and prefer each other to their partners in , blocking . Contradiction.

Receiver-pessimality (McVitie & Wilson 1971): in the proposer-optimal matching, each woman gets her worst valid partner. Combined with the above, stable matchings form a distributive lattice with the two Gale–Shapley outcomes as its extremes (Knuth, Mariages stables, 1976).

Complexity

AlgorithmTime (worst)Typical behaviourSpace
Bipartite check (BFS)linear
Kuhnmuch faster with a greedy warm start and random vertex order; worst cases exist
Hopcroft–Karpfew phases on random graphs; dense graphs:
König cover from a max matching extra—
Hungarian (potentials + minv) for , i.e. close to worst on random dense matrices for the matrix, extra
Gale–Shapley proposals, each with a rank table— for rankings

Constants and cache behaviour: Kuhn and Hopcroft–Karp spend their time chasing adjacency lists, so a flat CSR layout (one int array of neighbours plus offsets, as in the memory lesson) is noticeably faster than vector<vector<int>> at edges. The Hungarian inner loop is a linear scan over a row of the cost matrix — perfectly sequential and cache-friendly. How close you get to the worst case depends heavily on the input. Measured with the Python implementation on this page (one machine, so treat as rough): a random matrix with entries up to took 4.7 s, while the structured matrix , which forces long searches, took 11 s at and 90 s at . Compiled C++ is typically one to two orders of magnitude faster, so a few thousand rows is the practical ceiling there and a few hundred in pure Python. Recursion depth in Kuhn and Hopcroft–Karp equals the augmenting path length, which can reach ; in Python, raise the recursion limit or convert to an explicit stack for beyond a few thousand.

The theoretical frontier for unweighted bipartite matching has moved: Hopcroft–Karp's stood for decades for sparse graphs, and the 2022 almost-linear-time max-flow algorithm of Chen, Kyng, Liu, Peng, Probst Gutenberg and Sachdeva implies for bipartite matching too. It is not a practical algorithm today; Hopcroft–Karp, Dinic and push-relabel remain what people run.

Implementation

Bipartite check with an odd-cycle certificate

from collections import deque


def two_colour(n: int, adj: list[list[int]]) -> tuple[list[int] | None, list[int] | None]:
    """Return (colour, None) if bipartite, else (None, odd_cycle as a vertex list)."""
    colour = [-1] * n
    parent = [-1] * n
    depth = [0] * n
    for root in range(n):
        if colour[root] != -1:
            continue
        colour[root] = 0
        q = deque([root])
        while q:
            x = q.popleft()
            for y in adj[x]:
                if colour[y] == -1:
                    colour[y] = colour[x] ^ 1
                    parent[y], depth[y] = x, depth[x] + 1
                    q.append(y)
                elif colour[y] == colour[x]:
                    # walk both ends up the BFS tree to their lowest common ancestor
                    a, b, left, right = x, y, [], []
                    while depth[a] > depth[b]:
                        left.append(a); a = parent[a]
                    while depth[b] > depth[a]:
                        right.append(b); b = parent[b]
                    while a != b:
                        left.append(a); a = parent[a]
                        right.append(b); b = parent[b]
                    return None, left + [a] + right[::-1]
    return colour, None


def edges_to_adj(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b); adj[b].append(a)
    return adj


even_cycle = edges_to_adj(4, [(0, 1), (1, 2), (2, 3), (3, 0)])
col, cyc = two_colour(4, even_cycle)
assert cyc is None and all(col[a] != col[b] for a in range(4) for b in even_cycle[a])

triangle_plus = edges_to_adj(5, [(0, 1), (1, 2), (2, 0), (2, 3), (3, 4)])
col, cyc = two_colour(5, triangle_plus)
assert col is None and len(cyc) % 2 == 1 and sorted(cyc) == [0, 1, 2]
print("two-colouring ok")

Kuhn's algorithm

import sys


def max_matching_kuhn(n_left: int, n_right: int, adj: list[list[int]]) -> tuple[int, list[int]]:
    """Return (size, match_r) where match_r[v] is the left partner of right vertex v or -1."""
    sys.setrecursionlimit(max(1000, 4 * n_left + 100))
    match_r = [-1] * n_right

    def try_kuhn(u: int, seen: list[bool]) -> bool:
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                if match_r[v] == -1 or try_kuhn(match_r[v], seen):
                    match_r[v] = u
                    return True
        return False

    size = 0
    for u in range(n_left):
        if try_kuhn(u, [False] * n_right):
            size += 1
    return size, match_r


if __name__ == "__main__":
    size, match_r = max_matching_kuhn(4, 4, [[0, 1], [0, 3], [2], [1]])
    assert size == 4 and match_r == [0, 3, 2, 1]
    assert max_matching_kuhn(4, 4, [[0, 1], [0], [0, 2, 3], [0]])[0] == 3
    assert max_matching_kuhn(2, 3, [[], []])[0] == 0
    assert max_matching_kuhn(3, 3, [[0, 1, 2]] * 3)[0] == 3
    print("kuhn ok")
import java.util.Arrays;
import java.util.List;

public class Kuhn {
    private final List<int[]> adj;
    private final int[] matchR;
    private boolean[] seen;

    Kuhn(int nRight, List<int[]> adj) {
        this.adj = adj;
        this.matchR = new int[nRight];
        Arrays.fill(matchR, -1);
    }

    private boolean tryKuhn(int u) {
        for (int v : adj.get(u)) {
            if (seen[v]) continue;
            seen[v] = true;
            if (matchR[v] == -1 || tryKuhn(matchR[v])) {
                matchR[v] = u;
                return true;
            }
        }
        return false;
    }

    int solve() {
        int size = 0;
        for (int u = 0; u < adj.size(); u++) {
            seen = new boolean[matchR.length];
            if (tryKuhn(u)) size++;
        }
        return size;
    }

    public static void main(String[] args) {
        Kuhn k = new Kuhn(4, List.of(new int[]{0, 1}, new int[]{0, 3}, new int[]{2}, new int[]{1}));
        if (k.solve() != 4 || !Arrays.equals(k.matchR, new int[]{0, 3, 2, 1})) throw new AssertionError("trace graph");
        Kuhn k2 = new Kuhn(4, List.of(new int[]{0, 1}, new int[]{0}, new int[]{0, 2, 3}, new int[]{0}));
        if (k2.solve() != 3) throw new AssertionError("konig graph");
        Kuhn k3 = new Kuhn(3, List.of(new int[]{}, new int[]{}));
        if (k3.solve() != 0) throw new AssertionError("empty");
        int[] all = {0, 1, 2};
        Kuhn k4 = new Kuhn(3, List.of(all, all, all));
        if (k4.solve() != 3) throw new AssertionError("complete");
        System.out.println("kuhn ok");
    }
}
#include <cassert>
#include <functional>
#include <iostream>
#include <utility>
#include <vector>

std::pair<int, std::vector<int>> maxMatchingKuhn(int nLeft, int nRight, const std::vector<std::vector<int>>& adj) {
    std::vector<int> matchR(nRight, -1);
    std::vector<char> seen;
    std::function<bool(int)> tryKuhn = [&](int u) -> bool {
        for (int v : adj[u]) {
            if (seen[v]) continue;
            seen[v] = 1;
            if (matchR[v] == -1 || tryKuhn(matchR[v])) {
                matchR[v] = u;
                return true;
            }
        }
        return false;
    };
    int size = 0;
    for (int u = 0; u < nLeft; ++u) {
        seen.assign(nRight, 0);
        if (tryKuhn(u)) ++size;
    }
    return {size, matchR};
}

int main() {
    auto [size, matchR] = maxMatchingKuhn(4, 4, {{0, 1}, {0, 3}, {2}, {1}});
    assert(size == 4 && (matchR == std::vector<int>{0, 3, 2, 1}));
    assert(maxMatchingKuhn(4, 4, {{0, 1}, {0}, {0, 2, 3}, {0}}).first == 3);
    assert(maxMatchingKuhn(2, 3, {{}, {}}).first == 0);
    assert(maxMatchingKuhn(3, 3, {{0, 1, 2}, {0, 1, 2}, {0, 1, 2}}).first == 3);
    std::cout << "kuhn ok\n";
}
function maxMatchingKuhn(nLeft: number, nRight: number, adj: number[][]): [number, number[]] {
  const matchR: number[] = new Array(nRight).fill(-1);
  let seen: boolean[] = [];
  const tryKuhn = (u: number): boolean => {
    for (const v of adj[u]) {
      if (seen[v]) continue;
      seen[v] = true;
      if (matchR[v] === -1 || tryKuhn(matchR[v])) {
        matchR[v] = u;
        return true;
      }
    }
    return false;
  };
  let size = 0;
  for (let u = 0; u < nLeft; u++) {
    seen = new Array(nRight).fill(false);
    if (tryKuhn(u)) size++;
  }
  return [size, matchR];
}

function check(cond: boolean, msg: string): void {
  if (!cond) throw new Error(msg);
}

const [size, matchR] = maxMatchingKuhn(4, 4, [[0, 1], [0, 3], [2], [1]]);
check(size === 4 && matchR.join(",") === "0,3,2,1", "trace graph");
check(maxMatchingKuhn(4, 4, [[0, 1], [0], [0, 2, 3], [0]])[0] === 3, "konig graph");
check(maxMatchingKuhn(2, 3, [[], []])[0] === 0, "empty");
check(maxMatchingKuhn(3, 3, [[0, 1, 2], [0, 1, 2], [0, 1, 2]])[0] === 3, "complete");
console.log("kuhn ok");

Hopcroft–Karp with a König vertex cover

The BFS stops expanding at the first layer that touches a free right vertex (limit), and the DFS accepts a free right vertex only from that layer, so every path flipped in a phase is a shortest one — what the analysis assumes. it[u] is the current-arc pointer.

import sys
from collections import deque


def hopcroft_karp(n_left: int, n_right: int, adj: list[list[int]]):
    """Return (size, match_l, match_r)."""
    sys.setrecursionlimit(max(1000, 4 * n_left + 100))
    INF = float("inf")
    match_l, match_r = [-1] * n_left, [-1] * n_right
    dist = [0] * n_left
    it = [0] * n_left

    def bfs() -> float:
        q = deque()
        for u in range(n_left):
            if match_l[u] == -1:
                dist[u] = 0
                q.append(u)
            else:
                dist[u] = INF
        limit = INF
        while q:
            u = q.popleft()
            if dist[u] >= limit:
                continue
            for v in adj[u]:
                w = match_r[v]
                if w == -1:
                    limit = min(limit, dist[u])      # a shortest augmenting path ends here
                elif dist[w] == INF:
                    dist[w] = dist[u] + 1
                    q.append(w)
        return limit

    def dfs(u: int, limit: float) -> bool:
        while it[u] < len(adj[u]):
            v = adj[u][it[u]]
            w = match_r[v]
            if (w == -1 and dist[u] == limit) or (w != -1 and dist[w] == dist[u] + 1 and dfs(w, limit)):
                match_l[u], match_r[v] = v, u
                return True
            it[u] += 1
        dist[u] = INF                                # dead for the rest of this phase
        return False

    size = 0
    while (limit := bfs()) != INF:
        it = [0] * n_left
        for u in range(n_left):
            if match_l[u] == -1 and dfs(u, limit):
                size += 1
    return size, match_l, match_r


def konig_cover(n_left, n_right, adj, match_l, match_r):
    """Minimum vertex cover (left_ids, right_ids) from a maximum matching."""
    in_z_l, in_z_r = [False] * n_left, [False] * n_right
    q = deque(u for u in range(n_left) if match_l[u] == -1)
    for u in q:
        in_z_l[u] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v != match_l[u] and not in_z_r[v]:   # non-matching edge L -> R
                in_z_r[v] = True
                w = match_r[v]                       # matching edge R -> L
                if w != -1 and not in_z_l[w]:
                    in_z_l[w] = True
                    q.append(w)
    return [u for u in range(n_left) if not in_z_l[u]], [v for v in range(n_right) if in_z_r[v]]


if __name__ == "__main__":
    size, ml, mr = hopcroft_karp(4, 4, [[0, 1], [0, 3], [2], [1]])
    assert size == 4 and sorted(ml) == [0, 1, 2, 3]
    g = [[0, 1], [0], [0, 2, 3], [0]]
    size, ml, mr = hopcroft_karp(4, 4, g)
    assert size == 3
    cl, cr = konig_cover(4, 4, g, ml, mr)
    assert (cl, cr) == ([0, 2], [0])
    assert all(u in cl or v in cr for u in range(4) for v in g[u])
    assert hopcroft_karp(2, 3, [[], []])[0] == 0
    assert hopcroft_karp(3, 3, [[0, 1, 2]] * 3)[0] == 3
    print("hopcroft-karp ok")
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class HopcroftKarp {
    static final int INF = Integer.MAX_VALUE;
    final int nL, nR;
    final int[][] adj;
    final int[] matchL, matchR, dist, it;
    int limit;

    HopcroftKarp(int nL, int nR, int[][] adj) {
        this.nL = nL; this.nR = nR; this.adj = adj;
        matchL = new int[nL]; matchR = new int[nR]; dist = new int[nL]; it = new int[nL];
        Arrays.fill(matchL, -1);
        Arrays.fill(matchR, -1);
    }

    boolean bfs() {
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int u = 0; u < nL; u++) {
            if (matchL[u] == -1) { dist[u] = 0; q.add(u); } else dist[u] = INF;
        }
        limit = INF;
        while (!q.isEmpty()) {
            int u = q.poll();
            if (dist[u] >= limit) continue;
            for (int v : adj[u]) {
                int w = matchR[v];
                if (w == -1) limit = Math.min(limit, dist[u]);
                else if (dist[w] == INF) { dist[w] = dist[u] + 1; q.add(w); }
            }
        }
        return limit != INF;
    }

    boolean dfs(int u) {
        for (; it[u] < adj[u].length; it[u]++) {
            int v = adj[u][it[u]], w = matchR[v];
            if ((w == -1 && dist[u] == limit) || (w != -1 && dist[w] != INF && dist[w] == dist[u] + 1 && dfs(w))) {
                matchL[u] = v; matchR[v] = u;
                return true;
            }
        }
        dist[u] = INF;
        return false;
    }

    int solve() {
        int size = 0;
        while (bfs()) {
            Arrays.fill(it, 0);
            for (int u = 0; u < nL; u++) if (matchL[u] == -1 && dfs(u)) size++;
        }
        return size;
    }

    /** Returns {leftCover, rightCover}. Call after solve(). */
    List<List<Integer>> konigCover() {
        boolean[] zl = new boolean[nL], zr = new boolean[nR];
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int u = 0; u < nL; u++) if (matchL[u] == -1) { zl[u] = true; q.add(u); }
        while (!q.isEmpty()) {
            int u = q.poll();
            for (int v : adj[u]) {
                if (v == matchL[u] || zr[v]) continue;
                zr[v] = true;
                int w = matchR[v];
                if (w != -1 && !zl[w]) { zl[w] = true; q.add(w); }
            }
        }
        List<Integer> cl = new ArrayList<>(), cr = new ArrayList<>();
        for (int u = 0; u < nL; u++) if (!zl[u]) cl.add(u);
        for (int v = 0; v < nR; v++) if (zr[v]) cr.add(v);
        return List.of(cl, cr);
    }

    public static void main(String[] args) {
        if (new HopcroftKarp(4, 4, new int[][]{{0, 1}, {0, 3}, {2}, {1}}).solve() != 4) throw new AssertionError("trace");
        int[][] g = {{0, 1}, {0}, {0, 2, 3}, {0}};
        HopcroftKarp hk = new HopcroftKarp(4, 4, g);
        if (hk.solve() != 3) throw new AssertionError("konig size");
        List<List<Integer>> c = hk.konigCover();
        if (!c.get(0).equals(List.of(0, 2)) || !c.get(1).equals(List.of(0))) throw new AssertionError("cover " + c);
        if (new HopcroftKarp(2, 3, new int[][]{{}, {}}).solve() != 0) throw new AssertionError("empty");
        int[] all = {0, 1, 2};
        if (new HopcroftKarp(3, 3, new int[][]{all, all, all}).solve() != 3) throw new AssertionError("complete");
        System.out.println("hopcroft-karp ok");
    }
}
#include <cassert>
#include <climits>
#include <iostream>
#include <queue>
#include <utility>
#include <vector>

struct HopcroftKarp {
    int nL, nR, limit = INT_MAX;
    std::vector<std::vector<int>> adj;
    std::vector<int> matchL, matchR, dist, it;

    HopcroftKarp(int nl, int nr, std::vector<std::vector<int>> g)
        : nL(nl), nR(nr), adj(std::move(g)), matchL(nl, -1), matchR(nr, -1), dist(nl), it(nl) {}

    bool bfs() {
        std::queue<int> q;
        for (int u = 0; u < nL; ++u) {
            if (matchL[u] == -1) { dist[u] = 0; q.push(u); } else dist[u] = INT_MAX;
        }
        limit = INT_MAX;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            if (dist[u] >= limit) continue;
            for (int v : adj[u]) {
                int w = matchR[v];
                if (w == -1) limit = std::min(limit, dist[u]);
                else if (dist[w] == INT_MAX) { dist[w] = dist[u] + 1; q.push(w); }
            }
        }
        return limit != INT_MAX;
    }

    bool dfs(int u) {
        for (; it[u] < (int)adj[u].size(); ++it[u]) {
            int v = adj[u][it[u]], w = matchR[v];
            if ((w == -1 && dist[u] == limit) ||
                (w != -1 && dist[w] != INT_MAX && dist[w] == dist[u] + 1 && dfs(w))) {
                matchL[u] = v; matchR[v] = u;
                return true;
            }
        }
        dist[u] = INT_MAX;
        return false;
    }

    int solve() {
        int size = 0;
        while (bfs()) {
            std::fill(it.begin(), it.end(), 0);
            for (int u = 0; u < nL; ++u)
                if (matchL[u] == -1 && dfs(u)) ++size;
        }
        return size;
    }

    std::pair<std::vector<int>, std::vector<int>> konigCover() const {
        std::vector<char> zl(nL, 0), zr(nR, 0);
        std::queue<int> q;
        for (int u = 0; u < nL; ++u) if (matchL[u] == -1) { zl[u] = 1; q.push(u); }
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (v == matchL[u] || zr[v]) continue;
                zr[v] = 1;
                int w = matchR[v];
                if (w != -1 && !zl[w]) { zl[w] = 1; q.push(w); }
            }
        }
        std::vector<int> cl, cr;
        for (int u = 0; u < nL; ++u) if (!zl[u]) cl.push_back(u);
        for (int v = 0; v < nR; ++v) if (zr[v]) cr.push_back(v);
        return {cl, cr};
    }
};

int main() {
    assert(HopcroftKarp(4, 4, {{0, 1}, {0, 3}, {2}, {1}}).solve() == 4);
    HopcroftKarp hk(4, 4, {{0, 1}, {0}, {0, 2, 3}, {0}});
    assert(hk.solve() == 3);
    auto [cl, cr] = hk.konigCover();
    assert((cl == std::vector<int>{0, 2}) && (cr == std::vector<int>{0}));
    assert(HopcroftKarp(2, 3, {{}, {}}).solve() == 0);
    assert(HopcroftKarp(3, 3, {{0, 1, 2}, {0, 1, 2}, {0, 1, 2}}).solve() == 3);
    std::cout << "hopcroft-karp ok\n";
}
function hopcroftKarp(nL: number, nR: number, adj: number[][]): { size: number; matchL: number[]; matchR: number[] } {
  const INF = Number.MAX_SAFE_INTEGER;
  const matchL: number[] = new Array(nL).fill(-1);
  const matchR: number[] = new Array(nR).fill(-1);
  const dist: number[] = new Array(nL).fill(0);
  let it: number[] = new Array(nL).fill(0);
  let limit = INF;

  const bfs = (): boolean => {
    const q: number[] = [];
    for (let u = 0; u < nL; u++) {
      if (matchL[u] === -1) { dist[u] = 0; q.push(u); } else dist[u] = INF;
    }
    limit = INF;
    for (let h = 0; h < q.length; h++) {
      const u = q[h];
      if (dist[u] >= limit) continue;
      for (const v of adj[u]) {
        const w = matchR[v];
        if (w === -1) limit = Math.min(limit, dist[u]);
        else if (dist[w] === INF) { dist[w] = dist[u] + 1; q.push(w); }
      }
    }
    return limit !== INF;
  };

  const dfs = (u: number): boolean => {
    for (; it[u] < adj[u].length; it[u]++) {
      const v = adj[u][it[u]];
      const w = matchR[v];
      if ((w === -1 && dist[u] === limit) || (w !== -1 && dist[w] !== INF && dist[w] === dist[u] + 1 && dfs(w))) {
        matchL[u] = v; matchR[v] = u;
        return true;
      }
    }
    dist[u] = INF;
    return false;
  };

  let size = 0;
  while (bfs()) {
    it = new Array(nL).fill(0);
    for (let u = 0; u < nL; u++) if (matchL[u] === -1 && dfs(u)) size++;
  }
  return { size, matchL, matchR };
}

function konigCover(nL: number, nR: number, adj: number[][], matchL: number[], matchR: number[]): [number[], number[]] {
  const zl: boolean[] = new Array(nL).fill(false);
  const zr: boolean[] = new Array(nR).fill(false);
  const q: number[] = [];
  for (let u = 0; u < nL; u++) if (matchL[u] === -1) { zl[u] = true; q.push(u); }
  for (let h = 0; h < q.length; h++) {
    const u = q[h];
    for (const v of adj[u]) {
      if (v === matchL[u] || zr[v]) continue;
      zr[v] = true;
      const w = matchR[v];
      if (w !== -1 && !zl[w]) { zl[w] = true; q.push(w); }
    }
  }
  const cl: number[] = [];
  const cr: number[] = [];
  for (let u = 0; u < nL; u++) if (!zl[u]) cl.push(u);
  for (let v = 0; v < nR; v++) if (zr[v]) cr.push(v);
  return [cl, cr];
}

function check(cond: boolean, msg: string): void {
  if (!cond) throw new Error(msg);
}

check(hopcroftKarp(4, 4, [[0, 1], [0, 3], [2], [1]]).size === 4, "trace");
const g = [[0, 1], [0], [0, 2, 3], [0]];
const r = hopcroftKarp(4, 4, g);
check(r.size === 3, "konig size");
const [cl, cr] = konigCover(4, 4, g, r.matchL, r.matchR);
check(cl.join(",") === "0,2" && cr.join(",") === "0", "cover");
check(hopcroftKarp(2, 3, [[], []]).size === 0, "empty");
check(hopcroftKarp(3, 3, [[0, 1, 2], [0, 1, 2], [0, 1, 2]]).size === 3, "complete");
console.log("hopcroft-karp ok");

Hungarian algorithm,

This is the potentials-and-minv formulation (cp-algorithms, "Hungarian algorithm for solving the assignment problem"). Rows and columns are 1-indexed internally; column 0 is a sentinel that holds the row currently being inserted. It requires (rows ≤ columns); transpose otherwise. The minimum cost is at the end, and the code also checks it against the assignment.

def hungarian(cost: list[list[int]]) -> tuple[int, list[int]]:
    """Min-cost assignment of every row to a distinct column (rows <= cols). Returns (cost, col_of_row)."""
    n, m = len(cost), len(cost[0])
    assert n <= m
    INF = float("inf")
    u = [0] * (n + 1)          # row potentials
    v = [0] * (m + 1)          # column potentials
    p = [0] * (m + 1)          # p[j] = row matched to column j (0 = none); p[0] = row being inserted
    way = [0] * (m + 1)        # way[j] = previous column on the shortest alternating path to j
    for i in range(1, n + 1):
        p[0] = i
        j0 = 0
        minv = [INF] * (m + 1)
        used = [False] * (m + 1)
        while True:                                  # Dijkstra on reduced costs
            used[j0] = True
            i0, delta, j1 = p[j0], INF, 0
            for j in range(1, m + 1):
                if not used[j]:
                    cur = cost[i0 - 1][j - 1] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j], way[j] = cur, j0
                    if minv[j] < delta:
                        delta, j1 = minv[j], j
            for j in range(m + 1):                   # potential update keeps reduced costs >= 0
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0:                           # reached a free column
                break
        while j0:                                    # flip the augmenting path
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1
    col_of_row = [0] * n
    for j in range(1, m + 1):
        if p[j]:
            col_of_row[p[j] - 1] = j - 1
    total = sum(cost[i][col_of_row[i]] for i in range(n))
    assert total == -v[0]
    return total, col_of_row


if __name__ == "__main__":
    c = [[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 9, 4]]
    assert hungarian(c) == (13, [1, 0, 2, 3])
    assert hungarian([[5]]) == (5, [0])
    assert hungarian([[4, 1, 3], [2, 0, 5]])[0] == 3
    profit = [[3, 1], [2, 2]]                        # maximise by negating
    assert -hungarian([[-x for x in row] for row in profit])[0] == 5
    print("hungarian ok")
import java.util.Arrays;

public class Hungarian {
    /** Returns {totalCost, colOfRow[0], colOfRow[1], ...}. Requires rows <= cols. */
    static long[] solve(long[][] cost) {
        int n = cost.length, m = cost[0].length;
        final long INF = Long.MAX_VALUE / 4;
        long[] u = new long[n + 1], v = new long[m + 1];
        int[] p = new int[m + 1], way = new int[m + 1];
        for (int i = 1; i <= n; i++) {
            p[0] = i;
            int j0 = 0;
            long[] minv = new long[m + 1];
            Arrays.fill(minv, INF);
            boolean[] used = new boolean[m + 1];
            do {
                used[j0] = true;
                int i0 = p[j0], j1 = 0;
                long delta = INF;
                for (int j = 1; j <= m; j++) {
                    if (used[j]) continue;
                    long cur = cost[i0 - 1][j - 1] - u[i0] - v[j];
                    if (cur < minv[j]) { minv[j] = cur; way[j] = j0; }
                    if (minv[j] < delta) { delta = minv[j]; j1 = j; }
                }
                for (int j = 0; j <= m; j++) {
                    if (used[j]) { u[p[j]] += delta; v[j] -= delta; } else minv[j] -= delta;
                }
                j0 = j1;
            } while (p[j0] != 0);
            do {
                int j1 = way[j0];
                p[j0] = p[j1];
                j0 = j1;
            } while (j0 != 0);
        }
        long[] out = new long[n + 1];
        for (int j = 1; j <= m; j++) if (p[j] != 0) out[p[j]] = j - 1;
        long total = 0;
        for (int i = 0; i < n; i++) total += cost[i][(int) out[i + 1]];
        if (total != -v[0]) throw new AssertionError("dual mismatch");
        out[0] = total;
        return out;
    }

    public static void main(String[] args) {
        long[][] c = {{9, 2, 7, 8}, {6, 4, 3, 7}, {5, 8, 1, 8}, {7, 6, 9, 4}};
        if (!Arrays.equals(solve(c), new long[]{13, 1, 0, 2, 3})) throw new AssertionError("4x4");
        if (solve(new long[][]{{5}})[0] != 5) throw new AssertionError("1x1");
        if (solve(new long[][]{{4, 1, 3}, {2, 0, 5}})[0] != 3) throw new AssertionError("2x3");
        if (-solve(new long[][]{{-3, -1}, {-2, -2}})[0] != 5) throw new AssertionError("max");
        System.out.println("hungarian ok");
    }
}
#include <cassert>
#include <iostream>
#include <limits>
#include <utility>
#include <vector>

// Returns (min cost, colOfRow). Requires rows <= cols.
std::pair<long long, std::vector<int>> hungarian(const std::vector<std::vector<long long>>& cost) {
    int n = (int)cost.size(), m = (int)cost[0].size();
    const long long INF = std::numeric_limits<long long>::max() / 4;
    std::vector<long long> u(n + 1, 0), v(m + 1, 0);
    std::vector<int> p(m + 1, 0), way(m + 1, 0);
    for (int i = 1; i <= n; ++i) {
        p[0] = i;
        int j0 = 0;
        std::vector<long long> minv(m + 1, INF);
        std::vector<char> used(m + 1, 0);
        do {
            used[j0] = 1;
            int i0 = p[j0], j1 = 0;
            long long delta = INF;
            for (int j = 1; j <= m; ++j) {
                if (used[j]) continue;
                long long cur = cost[i0 - 1][j - 1] - u[i0] - v[j];
                if (cur < minv[j]) { minv[j] = cur; way[j] = j0; }
                if (minv[j] < delta) { delta = minv[j]; j1 = j; }
            }
            for (int j = 0; j <= m; ++j) {
                if (used[j]) { u[p[j]] += delta; v[j] -= delta; } else minv[j] -= delta;
            }
            j0 = j1;
        } while (p[j0] != 0);
        do {
            int j1 = way[j0];
            p[j0] = p[j1];
            j0 = j1;
        } while (j0 != 0);
    }
    std::vector<int> colOfRow(n);
    for (int j = 1; j <= m; ++j) if (p[j]) colOfRow[p[j] - 1] = j - 1;
    long long total = 0;
    for (int i = 0; i < n; ++i) total += cost[i][colOfRow[i]];
    assert(total == -v[0]);
    return {total, colOfRow};
}

int main() {
    auto [c, assign] = hungarian({{9, 2, 7, 8}, {6, 4, 3, 7}, {5, 8, 1, 8}, {7, 6, 9, 4}});
    assert(c == 13 && (assign == std::vector<int>{1, 0, 2, 3}));
    assert(hungarian({{5}}).first == 5);
    assert(hungarian({{4, 1, 3}, {2, 0, 5}}).first == 3);
    assert(-hungarian({{-3, -1}, {-2, -2}}).first == 5);
    std::cout << "hungarian ok\n";
}
function hungarian(cost: number[][]): [number, number[]] {
  const n = cost.length;
  const m = cost[0].length;
  const INF = Number.POSITIVE_INFINITY;
  const u: number[] = new Array(n + 1).fill(0);
  const v: number[] = new Array(m + 1).fill(0);
  const p: number[] = new Array(m + 1).fill(0);
  const way: number[] = new Array(m + 1).fill(0);
  for (let i = 1; i <= n; i++) {
    p[0] = i;
    let j0 = 0;
    const minv: number[] = new Array(m + 1).fill(INF);
    const used: boolean[] = new Array(m + 1).fill(false);
    do {
      used[j0] = true;
      const i0 = p[j0];
      let delta = INF;
      let j1 = 0;
      for (let j = 1; j <= m; j++) {
        if (used[j]) continue;
        const cur = cost[i0 - 1][j - 1] - u[i0] - v[j];
        if (cur < minv[j]) { minv[j] = cur; way[j] = j0; }
        if (minv[j] < delta) { delta = minv[j]; j1 = j; }
      }
      for (let j = 0; j <= m; j++) {
        if (used[j]) { u[p[j]] += delta; v[j] -= delta; } else minv[j] -= delta;
      }
      j0 = j1;
    } while (p[j0] !== 0);
    do {
      const j1 = way[j0];
      p[j0] = p[j1];
      j0 = j1;
    } while (j0 !== 0);
  }
  const colOfRow: number[] = new Array(n).fill(0);
  for (let j = 1; j <= m; j++) if (p[j] !== 0) colOfRow[p[j] - 1] = j - 1;
  let total = 0;
  for (let i = 0; i < n; i++) total += cost[i][colOfRow[i]];
  if (total !== -v[0]) throw new Error("dual mismatch");
  return [total, colOfRow];
}

function check(cond: boolean, msg: string): void {
  if (!cond) throw new Error(msg);
}

const [total, assign] = hungarian([[9, 2, 7, 8], [6, 4, 3, 7], [5, 8, 1, 8], [7, 6, 9, 4]]);
check(total === 13 && assign.join(",") === "1,0,2,3", "4x4");
check(hungarian([[5]])[0] === 5, "1x1");
check(hungarian([[4, 1, 3], [2, 0, 5]])[0] === 3, "2x3");
check(-hungarian([[-3, -1], [-2, -2]])[0] === 5, "max");
console.log("hungarian ok");

Gale–Shapley

from collections import deque


def gale_shapley(proposer_pref: list[list[int]], receiver_pref: list[list[int]]) -> list[int]:
    """Proposer-optimal stable matching. Returns partner[p] for each proposer p."""
    n = len(proposer_pref)
    rank = [[0] * n for _ in range(n)]               # rank[r][p]: lower is better
    for r in range(n):
        for pos, p in enumerate(receiver_pref[r]):
            rank[r][p] = pos
    next_choice = [0] * n
    partner_of_receiver = [-1] * n
    free = deque(range(n))
    while free:
        p = free.popleft()
        r = proposer_pref[p][next_choice[p]]
        next_choice[p] += 1
        cur = partner_of_receiver[r]
        if cur == -1:
            partner_of_receiver[r] = p
        elif rank[r][p] < rank[r][cur]:
            partner_of_receiver[r] = p
            free.append(cur)
        else:
            free.append(p)
    partner = [-1] * n
    for r, p in enumerate(partner_of_receiver):
        partner[p] = r
    return partner


def is_stable(pp, rp, partner):
    n = len(pp)
    holder = [0] * n
    for p, r in enumerate(partner):
        holder[r] = p
    for p in range(n):
        for r in pp[p]:
            if r == partner[p]:
                break                                # p prefers nobody further down
            if rp[r].index(p) < rp[r].index(holder[r]):
                return False                         # (p, r) is a blocking pair
    return True


if __name__ == "__main__":
    men = [[1, 0, 2, 3], [0, 2, 3, 1], [1, 0, 2, 3], [1, 2, 3, 0]]
    women = [[0, 3, 2, 1], [1, 3, 2, 0], [0, 3, 1, 2], [2, 1, 0, 3]]
    m = gale_shapley(men, women)
    assert m == [0, 2, 3, 1] and is_stable(men, women, m)
    w = gale_shapley(women, men)                     # women propose
    assert w == [0, 1, 3, 2] and is_stable(women, men, w)
    assert gale_shapley([[0]], [[0]]) == [0]
    print("gale-shapley ok")
import java.util.ArrayDeque;
import java.util.Arrays;

public class GaleShapley {
    static int[] match(int[][] proposerPref, int[][] receiverPref) {
        int n = proposerPref.length;
        int[][] rank = new int[n][n];
        for (int r = 0; r < n; r++)
            for (int pos = 0; pos < n; pos++) rank[r][receiverPref[r][pos]] = pos;
        int[] next = new int[n], holder = new int[n];
        Arrays.fill(holder, -1);
        ArrayDeque<Integer> free = new ArrayDeque<>();
        for (int p = 0; p < n; p++) free.add(p);
        while (!free.isEmpty()) {
            int p = free.poll();
            int r = proposerPref[p][next[p]++];
            int cur = holder[r];
            if (cur == -1) holder[r] = p;
            else if (rank[r][p] < rank[r][cur]) { holder[r] = p; free.add(cur); }
            else free.add(p);
        }
        int[] partner = new int[n];
        for (int r = 0; r < n; r++) partner[holder[r]] = r;
        return partner;
    }

    public static void main(String[] args) {
        int[][] men = {{1, 0, 2, 3}, {0, 2, 3, 1}, {1, 0, 2, 3}, {1, 2, 3, 0}};
        int[][] women = {{0, 3, 2, 1}, {1, 3, 2, 0}, {0, 3, 1, 2}, {2, 1, 0, 3}};
        if (!Arrays.equals(match(men, women), new int[]{0, 2, 3, 1})) throw new AssertionError("men propose");
        if (!Arrays.equals(match(women, men), new int[]{0, 1, 3, 2})) throw new AssertionError("women propose");
        if (!Arrays.equals(match(new int[][]{{0}}, new int[][]{{0}}), new int[]{0})) throw new AssertionError("1x1");
        System.out.println("gale-shapley ok");
    }
}
#include <cassert>
#include <deque>
#include <iostream>
#include <vector>

using Prefs = std::vector<std::vector<int>>;

std::vector<int> galeShapley(const Prefs& proposerPref, const Prefs& receiverPref) {
    int n = (int)proposerPref.size();
    std::vector<std::vector<int>> rank(n, std::vector<int>(n));
    for (int r = 0; r < n; ++r)
        for (int pos = 0; pos < n; ++pos) rank[r][receiverPref[r][pos]] = pos;
    std::vector<int> next(n, 0), holder(n, -1);
    std::deque<int> freeQ;
    for (int p = 0; p < n; ++p) freeQ.push_back(p);
    while (!freeQ.empty()) {
        int p = freeQ.front(); freeQ.pop_front();
        int r = proposerPref[p][next[p]++];
        int cur = holder[r];
        if (cur == -1) holder[r] = p;
        else if (rank[r][p] < rank[r][cur]) { holder[r] = p; freeQ.push_back(cur); }
        else freeQ.push_back(p);
    }
    std::vector<int> partner(n);
    for (int r = 0; r < n; ++r) partner[holder[r]] = r;
    return partner;
}

int main() {
    Prefs men = {{1, 0, 2, 3}, {0, 2, 3, 1}, {1, 0, 2, 3}, {1, 2, 3, 0}};
    Prefs women = {{0, 3, 2, 1}, {1, 3, 2, 0}, {0, 3, 1, 2}, {2, 1, 0, 3}};
    assert((galeShapley(men, women) == std::vector<int>{0, 2, 3, 1}));
    assert((galeShapley(women, men) == std::vector<int>{0, 1, 3, 2}));
    assert((galeShapley({{0}}, {{0}}) == std::vector<int>{0}));
    std::cout << "gale-shapley ok\n";
}
function galeShapley(proposerPref: number[][], receiverPref: number[][]): number[] {
  const n = proposerPref.length;
  const rank: number[][] = Array.from({ length: n }, () => new Array(n).fill(0));
  for (let r = 0; r < n; r++) for (let pos = 0; pos < n; pos++) rank[r][receiverPref[r][pos]] = pos;
  const next: number[] = new Array(n).fill(0);
  const holder: number[] = new Array(n).fill(-1);
  const free: number[] = [];
  for (let p = 0; p < n; p++) free.push(p);
  for (let h = 0; h < free.length; h++) {
    const p = free[h];
    const r = proposerPref[p][next[p]++];
    const cur = holder[r];
    if (cur === -1) holder[r] = p;
    else if (rank[r][p] < rank[r][cur]) { holder[r] = p; free.push(cur); }
    else free.push(p);
  }
  const partner: number[] = new Array(n).fill(-1);
  for (let r = 0; r < n; r++) partner[holder[r]] = r;
  return partner;
}

function check(cond: boolean, msg: string): void {
  if (!cond) throw new Error(msg);
}

const men = [[1, 0, 2, 3], [0, 2, 3, 1], [1, 0, 2, 3], [1, 2, 3, 0]];
const women = [[0, 3, 2, 1], [1, 3, 2, 0], [0, 3, 1, 2], [2, 1, 0, 3]];
check(galeShapley(men, women).join(",") === "0,2,3,1", "men propose");
check(galeShapley(women, men).join(",") === "0,1,3,2", "women propose");
check(galeShapley([[0]], [[0]]).join(",") === "0", "1x1");
console.log("gale-shapley ok");

Variant: minimum path cover in a DAG

def min_path_cover(n: int, edges: list[tuple[int, int]]) -> tuple[int, list[list[int]]]:
    """Vertex-disjoint path cover of a DAG via matching on the split graph."""
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)                    # a_out -- b_in
    match_r = [-1] * n                      # match_r[b] = predecessor of b on its path

    def try_kuhn(u, seen):
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                if match_r[v] == -1 or try_kuhn(match_r[v], seen):
                    match_r[v] = u
                    return True
        return False

    matched = sum(try_kuhn(u, [False] * n) for u in range(n))
    succ = [-1] * n
    for b, a in enumerate(match_r):
        if a != -1:
            succ[a] = b
    paths = []
    for start in range(n):
        if match_r[start] == -1:            # no predecessor: a path starts here
            path, x = [], start
            while x != -1:
                path.append(x)
                x = succ[x]
            paths.append(path)
    assert len(paths) == n - matched
    return n - matched, paths


k, paths = min_path_cover(4, [(0, 1), (0, 2), (1, 3), (2, 3)])          # a=0, b=1, c=2, d=3
assert k == 2 and sorted(v for p in paths for v in p) == [0, 1, 2, 3]
assert min_path_cover(3, [])[0] == 3
assert min_path_cover(4, [(0, 1), (1, 2), (2, 3)]) == (1, [[0, 1, 2, 3]])
print("path cover ok")

Real-world uses

Medical residency and school choice. The US National Resident Matching Program has used a stable-matching algorithm since the early 1950s. Roth (1984) showed that the algorithm the NRMP had used for decades was equivalent to hospital-proposing deferred acceptance — invented independently of Gale and Shapley. In 1998 the NRMP adopted the Roth–Peranson algorithm, an applicant-proposing variant that also handles couples who must be matched together (with couples, a stable matching may not exist, so the algorithm is a carefully engineered heuristic; Roth & Peranson 1999). Applicant-proposing matters because the proposing side gets its best stable outcome and cannot gain by misreporting preferences (Dubins & Freedman 1981; Roth 1982) — the receiving side can, in principle. Boston and New York public school assignment moved to deferred acceptance in the mid-2000s with Roth, Abdulkadiroğlu, Pathak and Sönmez as designers; kidney exchange programmes (also Roth's work) use matching and cycle-packing on compatibility graphs.

Assignment in operations. Ride-hailing dispatch, warehouse task assignment and crew pairing are assignment problems at heart, often solved in batches: collect requests for a few seconds, build a cost matrix (estimated pickup time), solve an assignment, dispatch. Public descriptions from ride-hailing companies describe batched matching in this spirit; the exact solvers are proprietary, so treat any specific claim about "company X runs the Hungarian algorithm" with suspicion. SciPy's scipy.optimize.linear_sum_assignment implements a shortest-augmenting-path variant (the Jonker–Volgenant-style algorithm described by Crouse, 2016), which is what most Python users actually call.

Multi-object tracking. Tracking pedestrians or cars in video matches detections in frame to tracks from frame , with cost = distance or 1 − IoU. The widely used SORT tracker (Bewley et al., 2016) solves this per frame with the Hungarian algorithm; the same pattern appears in radar tracking and in DETR-style object detectors, which use Hungarian matching between predictions and ground truth in their training loss (Carion et al., 2020).

Network switches. An input-queued crossbar switch must decide, every cell time, which input port sends to which output port — a bipartite matching between inputs and outputs recomputed millions of times per second. Exact maximum matching is too slow at that rate, so schedulers such as iSLIP (McKeown, 1999) compute fast maximal matchings with round-robin pointers, trading optimality for hardware simplicity — the greedy rung of the ladder above, chosen deliberately.

Scheduling. Assigning tasks to machines when each task needs exactly one compatible machine is matching; once machines have capacity > 1 or tasks have costs, it becomes flow — the next lesson — and the CPU scheduling page shows the OS-level analogue where decisions must be online.

Pitfalls & edge cases

  • Running bipartite theorems on non-bipartite graphs. König, Hall and are false with odd cycles: a triangle has but needs a 2-vertex cover. If you are pairing elements of one set, check bipartiteness or use blossom.
  • Forgetting to reset seen per root in Kuhn. Without the reset, later searches miss paths and return a non-maximum matching. With it reset inside the recursion, the DFS can loop forever.
  • Disconnected graphs in the 2-colouring. Loop over all roots; a single BFS only colours one component.
  • Index collisions between sides. If you store both sides in one array, right vertex is usually node . Mixing the two numbering schemes is the most common Kuhn bug.
  • Recursion depth. Augmenting paths can be long; Python's default limit (1000) fails on a path-like graph with a few thousand vertices. Raise the limit or make the DFS iterative.
  • Hopcroft–Karp that is secretly Kuhn. Omitting the dist[w] == dist[u] + 1 check, or resetting dist inside the phase, keeps the answer correct but loses the phase bound.
  • Hungarian with . The formulation requires rows ≤ columns; transpose and map the answer back.
  • Hungarian and forbidden pairs. Use a large finite cost, not inf (arithmetic on inf produces nan in floating point and overflow in integers), choose it larger than , and check whether the optimum used one.
  • Integer overflow in costs. Potentials can grow to about ; with and costs , that exceeds 32 bits. Use 64-bit.
  • Maximisation by "max − c". Works, but negation is simpler and avoids overflow when costs are large. Never mix the two in one matrix.
  • Gale–Shapley with incomplete lists or unequal sides. The basic algorithm assumes complete lists and equal . With incomplete lists, a proposer who exhausts their list stays single; with unequal sides the result is still stable but not perfect. Ties in preferences break the uniqueness of the optimal outcome and make "weakly stable" vs "strongly stable" a real distinction.
  • Confusing "maximal" with "maximum". A matching you cannot extend by one edge can still be half the optimum.

Variations

  • General (non-bipartite) matching: Edmonds' blossom algorithm (1965), in simple implementations, by Micali–Vazirani. Needed for roommates-style pairing in one set.
  • Maximum-weight matching (not necessarily perfect): add dummy vertices with zero-weight edges, or use min-cost flow and stop when the next augmenting path has non-negative cost.
  • b-matching / capacitated assignment: each vertex can be matched up to times — a flow problem with capacities on source and sink edges.
  • Online bipartite matching: right vertices arrive one at a time and must be matched immediately. Greedy is -competitive; the RANKING algorithm of Karp, Vazirani and Vazirani (1990) achieves in expectation, the foundation of ad-allocation theory (AdWords).
  • Stable roommates: stable matching in one set; may have no solution; Irving's algorithm (1985) finds one in or reports none.
  • Hospitals/residents (many-to-one): each hospital has a quota; Gale–Shapley extends directly, and the rural hospitals theorem says every stable matching fills the same positions.
  • Auction algorithm (Bertsekas, 1979): an alternative to Hungarian for assignment, naturally parallel, good for sparse problems.
  • Bitmask DP assignment: = best cost assigning the first rows to the columns in mask. Simpler than Hungarian for .

Practice ladder

Each problem is described in my own words; follow the link for the formal statement.

1. Is Graph Bipartite? (LeetCode 785) — Decide whether an undirected graph, possibly disconnected, can be two-coloured. Teaches the parity colouring and looping over components.

Hint

BFS from every uncoloured vertex; give neighbours the opposite colour; fail on an edge between equal colours.

2. Possible Bipartition (LeetCode 886) — Split people into two groups given a list of pairs who refuse to be together. Teaches recognising a bipartite check behind a story.

Hint

"Dislike" pairs are edges. The split exists if and only if the dislike graph has no odd cycle.

3. Building Teams (CSES 1668) — Assign each pupil to one of two teams so friends are on different teams, and print the assignment or report impossibility. Teaches outputting the colouring at scale.

Hint

Same as above at vertices; use an iterative BFS and print colour + 1.

4. School Dance (CSES 1696) — Given which boys and girls are willing to dance together, pair up as many as possible and print the pairs. Teaches maximum bipartite matching directly.

Hint

Kuhn is fast enough for 500 + 500 vertices and 1000 edges. Print match_r as pairs.

Solution
import sys


def school_dance(n_boys: int, n_girls: int, pairs: list[tuple[int, int]]) -> list[tuple[int, int]]:
    sys.setrecursionlimit(10000)
    adj = [[] for _ in range(n_boys + 1)]
    for b, g in pairs:
        adj[b].append(g)
    match_g = [0] * (n_girls + 1)                  # 0 = free (1-indexed input)

    def try_kuhn(b, seen):
        for g in adj[b]:
            if not seen[g]:
                seen[g] = True
                if match_g[g] == 0 or try_kuhn(match_g[g], seen):
                    match_g[g] = b
                    return True
        return False

    for b in range(1, n_boys + 1):
        try_kuhn(b, [False] * (n_girls + 1))
    return sorted((match_g[g], g) for g in range(1, n_girls + 1) if match_g[g])


res = school_dance(3, 2, [(1, 1), (1, 2), (2, 1), (3, 1)])
assert len(res) == 2 and len({b for b, _ in res}) == 2 and len({g for _, g in res}) == 2
assert school_dance(2, 2, [(1, 1), (2, 1)]) in ([(1, 1)], [(2, 1)])
print("1696 ok")

: at most steps.

5. Maximum Number of Accepted Invitations (LeetCode 1820) — Boys may invite girls they are compatible with (given as a grid); each person in at most one pair; maximise accepted invitations. Teaches matching from a 0/1 matrix (premium problem).

Hint

Rows are left vertices, columns right vertices, grid[i][j] == 1 is an edge. Kuhn over the matrix.

6. Coin Grid (CSES 1709) — Coins lie on some cells of an grid; one move removes every coin in a chosen row or column. Find the fewest moves and print them. Teaches König with an explicit cover.

Hint

Rows on the left, columns on the right, a coin at is an edge. A set of moves removes all coins iff it is a vertex cover. Run a matching, then extract the König cover.

Solution
from collections import deque
from itertools import combinations


def coin_grid(n: int, coins: list[tuple[int, int]]) -> list[tuple[str, int]]:
    adj = [[] for _ in range(n)]
    for r, c in coins:
        adj[r].append(c)
    match_l, match_r = [-1] * n, [-1] * n

    def try_kuhn(u, seen):
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                if match_r[v] == -1 or try_kuhn(match_r[v], seen):
                    match_r[v], match_l[u] = u, v
                    return True
        return False

    for u in range(n):
        try_kuhn(u, [False] * n)
    zl, zr = [False] * n, [False] * n                 # König: alternating BFS from free rows
    q = deque(u for u in range(n) if match_l[u] == -1)
    for u in q:
        zl[u] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v != match_l[u] and not zr[v]:
                zr[v] = True
                if match_r[v] != -1 and not zl[match_r[v]]:
                    zl[match_r[v]] = True
                    q.append(match_r[v])
    return [("row", r) for r in range(n) if not zl[r]] + [("col", c) for c in range(n) if zr[c]]


def brute(n, coins):
    lines = [("row", i) for i in range(n)] + [("col", i) for i in range(n)]
    for k in range(2 * n + 1):
        for chosen in combinations(lines, k):
            s = set(chosen)
            if all(("row", r) in s or ("col", c) in s for r, c in coins):
                return k


coins = [(0, 0), (0, 2), (1, 1), (2, 1)]
moves = coin_grid(3, coins)
assert len(moves) == brute(3, coins) == 2
assert all(("row", r) in moves or ("col", c) in moves for r, c in coins)
import random
random.seed(4)
for _ in range(200):
    n = random.randint(1, 4)
    cs = list({(random.randrange(n), random.randrange(n)) for _ in range(random.randint(0, 8))})
    mv = coin_grid(n, cs)
    assert len(mv) == brute(n, cs) and all(("row", r) in mv or ("col", c) in mv for r, c in cs)
print("1709 ok")

for coins with Kuhn; the cover extraction is linear.

7. Maximum Students Taking Exam (LeetCode 1349) — Seat as many students as possible on the good seats of a classroom so nobody can copy from the left, right, upper-left or upper-right neighbour. Teaches maximum independent set = seats − matching.

Hint

Every conflict joins columns and , so colouring by column parity makes the conflict graph bipartite. Answer = good seats − maximum matching. (The intended solution is a row-by-row bitmask DP; both work at 8 × 8.)

Solution
from functools import lru_cache
import random


def max_students(seats: list[list[str]]) -> int:
    rows, cols = len(seats), len(seats[0])
    good = [(r, c) for r in range(rows) for c in range(cols) if seats[r][c] == "."]
    idx = {cell: i for i, cell in enumerate(good)}
    adj = {i: [] for i in range(len(good))}
    for (r, c), i in idx.items():
        if c % 2 == 0:                                  # even columns on the left side
            for dr, dc in ((0, -1), (0, 1), (-1, -1), (-1, 1), (1, -1), (1, 1)):
                j = idx.get((r + dr, c + dc))
                if j is not None:
                    adj[i].append(j)
    match_r = {}

    def try_kuhn(u, seen):
        for v in adj[u]:
            if v not in seen:
                seen.add(v)
                if v not in match_r or try_kuhn(match_r[v], seen):
                    match_r[v] = u
                    return True
        return False

    matching = sum(try_kuhn(i, set()) for i in adj if good[i][1] % 2 == 0)
    return len(good) - matching


def brute(seats):
    rows, cols = len(seats), len(seats[0])

    @lru_cache(maxsize=None)
    def go(r, prev):
        if r == rows:
            return 0
        best = 0
        for mask in range(1 << cols):
            if any(mask >> c & 1 and seats[r][c] == "#" for c in range(cols)):
                continue
            if mask & (mask << 1) or mask & (prev << 1) or mask & (prev >> 1):
                continue
            best = max(best, bin(mask).count("1") + go(r + 1, mask))
        return best
    return go(0, 0)


ex1 = [list("#.##.#"), list(".####."), list("#.##.#")]
assert max_students(ex1) == brute(ex1) == 4
random.seed(9)
for _ in range(150):
    g = [[random.choice(".#") for _ in range(random.randint(1, 5))]]
    g += [[random.choice(".#") for _ in range(len(g[0]))] for _ in range(random.randint(0, 3))]
    assert max_students(g) == brute(g)
print("1349 ok")

with seats and — trivial. The brute force is the DP the problem setters intended.

8. Minimum Operations to Remove Adjacent Ones in Matrix (LeetCode 2123) — Flip the fewest 1s to 0 so no two 1s are 4-adjacent. Teaches minimum vertex cover on a grid graph (premium problem).

Hint

Cells with even vs odd form a bipartition of the grid. Edges join adjacent 1-cells. Answer = maximum matching (König).

9. Fast Maximum Matching (SPOJ MATCHING) — Maximum matching with up to 50 000 vertices per side and 150 000 edges. Teaches why Hopcroft–Karp exists.

Hint

Kuhn times out on adversarial tests. Use Hopcroft–Karp with the current-arc pointer and fast input.

10. Maximum Compatibility Score Sum (LeetCode 1947) — Pair students with mentors one-to-one to maximise the total number of matching survey answers. Teaches maximum-weight assignment.

Hint

, so permutations or bitmask DP pass; it is also a direct Hungarian on negated scores.

Solution
from itertools import permutations


def hungarian_min(cost):
    n, m = len(cost), len(cost[0])
    INF = float("inf")
    u, v, p, way = [0] * (n + 1), [0] * (m + 1), [0] * (m + 1), [0] * (m + 1)
    for i in range(1, n + 1):
        p[0], j0 = i, 0
        minv, used = [INF] * (m + 1), [False] * (m + 1)
        while True:
            used[j0] = True
            i0, delta, j1 = p[j0], INF, 0
            for j in range(1, m + 1):
                if not used[j]:
                    cur = cost[i0 - 1][j - 1] - u[i0] - v[j]
                    if cur < minv[j]:
                        minv[j], way[j] = cur, j0
                    if minv[j] < delta:
                        delta, j1 = minv[j], j
            for j in range(m + 1):
                if used[j]:
                    u[p[j]] += delta
                    v[j] -= delta
                else:
                    minv[j] -= delta
            j0 = j1
            if p[j0] == 0:
                break
        while j0:
            j1 = way[j0]
            p[j0] = p[j1]
            j0 = j1
    return -v[0]


def max_compatibility(students: list[list[int]], mentors: list[list[int]]) -> int:
    score = [[sum(a == b for a, b in zip(s, m)) for m in mentors] for s in students]
    return -hungarian_min([[-x for x in row] for row in score])


st = [[1, 1, 0], [1, 0, 1], [0, 0, 1]]
me = [[1, 0, 0], [0, 0, 1], [1, 1, 0]]
brute = max(sum(sum(a == b for a, b in zip(st[i], me[p[i]])) for i in range(3)) for p in permutations(range(3)))
assert max_compatibility(st, me) == brute == 8
assert max_compatibility([[0, 0], [0, 0], [0, 0]], [[1, 1], [1, 1], [1, 1]]) == 0
print("1947 ok")

for questions.

11. Maximum AND Sum of Array (LeetCode 2172) — Place numbers into numbered slots, each slot holding at most two, maximising the sum of number AND slot. Teaches turning capacities into duplicated columns.

Hint

Duplicate each slot into two columns and run a maximum-weight assignment (rows = numbers, columns = slot copies; rows ≤ columns). Base-3 DP over slots is the intended solution.

12. Campus Bikes II (LeetCode 1066) — Assign each worker a distinct bike to minimise the total Manhattan distance (premium problem). Teaches assignment with more columns than rows.

Hint

Rows = workers, columns = bikes, . Rectangular Hungarian, or bitmask DP over bikes.

13. Task Assignment (CSES 2129) — Assign employees to tasks at minimum total cost and print the assignment, . Teaches the full Hungarian algorithm with output.

Hint

The implementation above, printing col_of_row. Min-cost flow also passes at this size.

14. Stable Marriage Problem (SPOJ STABLEMP) — Given full preference lists for men and women, output a stable matching. Teaches Gale–Shapley with a rank table and fast input.

Hint

Build rank[w][m] once so each comparison is ; the whole run is for .

Solution
from collections import deque


def stable_marriage(men_pref: list[list[int]], women_pref: list[list[int]]) -> list[int]:
    n = len(men_pref)
    rank = [[0] * n for _ in range(n)]
    for w in range(n):
        for pos, m in enumerate(women_pref[w]):
            rank[w][m] = pos
    nxt, husband, free = [0] * n, [-1] * n, deque(range(n))
    while free:
        m = free.popleft()
        w = men_pref[m][nxt[m]]
        nxt[m] += 1
        if husband[w] == -1:
            husband[w] = m
        elif rank[w][m] < rank[w][husband[w]]:
            free.append(husband[w])
            husband[w] = m
        else:
            free.append(m)
    wife = [0] * n
    for w, m in enumerate(husband):
        wife[m] = w
    return wife


men = [[1, 0, 2, 3], [0, 2, 3, 1], [1, 0, 2, 3], [1, 2, 3, 0]]
women = [[0, 3, 2, 1], [1, 3, 2, 0], [0, 3, 1, 2], [2, 1, 0, 3]]
assert stable_marriage(men, women) == [0, 2, 3, 1]
print("stablemp ok")

time and space.

Common mistakes & interview follow-ups

"Why not greedy?" Greedy gives a maximal matching, which can be half the maximum. Draw L0–R0, L0–R1, L1–R0: greedy L0–R0 strands L1; the augmenting path L1–R0–L0–R1 fixes it.

"Prove your matching is maximum." Exhibit a vertex cover of the same size (König). It is a one-line certificate, checkable in , and interviewers love it.

"What if the graph is not bipartite?" Berge's theorem still holds but DFS-based augmenting path search can fail because of odd cycles; you need Edmonds' blossom algorithm. Say so rather than running Kuhn on it.

", — will Kuhn pass?" Not reliably: worst case . Use Hopcroft–Karp ( worst case, far less in practice) or Dinic on the unit network.

"Costs on edges now." Assignment: Hungarian for dense matrices up to the low thousands, min-cost flow for sparse graphs or capacities, bitmask DP for . Mention the dual certificate .

"Requests arrive online." You cannot augment backwards in time. Greedy is ½-competitive; randomised RANKING achieves . Most real dispatch systems batch requests over a short window and solve offline assignments per batch.

"In stable matching, who should propose?" The side whose welfare you want to maximise and whom you want to make strategy-proof: the proposers get their best stable partner and cannot benefit from lying. That is why the NRMP switched to applicant-proposing.

"Can a stable matching fail to exist?" Not in the bipartite, complete-list, no-couples setting (Gale–Shapley always finds one). With couples or in the one-sided roommates problem, yes.

Common mistakes interviewers watch for: not resetting seen; mixing left/right indices; claiming König for general graphs; Hungarian with inf costs; forgetting that "maximum independent set" is NP-hard in general and only easy here because of bipartiteness.

Quick quiz

1. A graph has a cycle of length 7. Can it be bipartite? What about a graph whose only cycles have lengths 4 and 6?

Answer

No — an odd cycle is a certificate of non-bipartiteness. A graph whose cycles are all even is bipartite (König's characterisation); BFS parity colouring will succeed.

2. In the Kuhn trace, why is R0 skipped when L0 is re-explored during the search from L1?

Answer

R0 was marked seen when L1 first tried it in the same search. Revisiting it would mean asking L0 to give up R0 in order to take R0 — a loop. The seen array prevents it.

3. A bipartite graph has 10 vertices and a maximum matching of size 4. What are the sizes of a minimum vertex cover and a maximum independent set?

Answer

Minimum vertex cover = 4 (König). Maximum independent set = (complement of a minimum cover).

4. After Hopcroft–Karp's phase , the shortest augmenting path has length 7. What can you say about the next phase?

Answer

Its shortest augmenting path has length at least 9: lengths are odd and strictly increase between phases.

5. In Gale–Shapley with men proposing, can a woman end up with her favourite stable partner?

Answer

Only if her best and worst stable partners coincide. In the men-proposing outcome every woman gets her worst stable partner (receiver-pessimality). In the example, w1 gets m3 (her 2nd) though m1 (her 1st) is a stable partner for her in the women-optimal matching.

Further reading / sources

  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4th ed. (2022), chapter 25 "Matchings in Bipartite Graphs" (25.1 Hopcroft–Karp, 25.2 stable marriage, 25.3 the Hungarian algorithm) and chapter 24 "Maximum Flow"; in the 3rd ed. (2009), §26.3 "Maximum bipartite matching".
  • J. Kleinberg, É. Tardos, Algorithm Design (2005), §1.1 (stable matching, with the proposer-optimality proof), §7.5 "Bipartite Matching Problem", §7.13 "Adding Costs to the Matching Problem".
  • cp-algorithms: Check whether a graph is bipartite, Kuhn's algorithm for maximum bipartite matching, Hungarian algorithm for the assignment problem.
  • C. Berge, "Two theorems in graph theory", PNAS 43(9), 1957. P. Hall, "On representatives of subsets", J. London Math. Soc. 10, 1935. D. Kőnig, "Gráfok és mátrixok", Matematikai és Fizikai Lapok 38, 1931.
  • J. E. Hopcroft, R. M. Karp, "An algorithm for maximum matchings in bipartite graphs", SIAM J. Computing 2(4), 1973.
  • H. W. Kuhn, "The Hungarian method for the assignment problem", Naval Research Logistics Quarterly 2, 1955. J. Munkres, "Algorithms for the assignment and transportation problems", J. SIAM 5(1), 1957. J. Edmonds, R. M. Karp, "Theoretical improvements in algorithmic efficiency for network flow problems", JACM 19(2), 1972.
  • D. Gale, L. S. Shapley, "College admissions and the stability of marriage", American Mathematical Monthly 69(1), 1962. D. G. McVitie, L. B. Wilson, "The stable marriage problem", CACM 14(7), 1971. D. E. Knuth, Mariages stables, 1976 (English: Stable Marriage and Its Relation to Other Combinatorial Problems, AMS 1997).
  • A. E. Roth, "The evolution of the labor market for medical interns and residents: a case study in game theory", J. Political Economy 92(6), 1984; A. E. Roth, E. Peranson, "The redesign of the matching market for American physicians", American Economic Review 89(4), 1999; L. E. Dubins, D. A. Freedman, "Machiavelli and the Gale–Shapley algorithm", American Mathematical Monthly 88(7), 1981.
  • R. M. Karp, U. V. Vazirani, V. V. Vazirani, "An optimal algorithm for on-line bipartite matching", STOC 1990. J. Edmonds, "Paths, trees, and flowers", Canadian J. Math. 17, 1965.
  • N. McKeown, "The iSLIP scheduling algorithm for input-queued switches", IEEE/ACM Trans. Networking 7(2), 1999.
  • D. F. Crouse, "On implementing 2D rectangular assignment algorithms", IEEE Trans. Aerospace and Electronic Systems 52(4), 2016 (the algorithm behind SciPy's linear_sum_assignment). A. Bewley et al., "Simple Online and Realtime Tracking", ICIP 2016.

Previous lesson: Euler & Hamiltonian Paths · Next lesson: Network Flow: Ford-Fulkerson, Edmonds-Karp, Dinic & Min-Cost Flow

Related: Graphs overview (Module 4) · BFS in Depth · DFS in Depth · Shortest Paths · Topological Sort & DAG DP · 2-SAT & Graph Coloring · Greedy Algorithms · Dynamic Programming · Course home