Bipartite Matching — Hopcroft-Karp + Hungarian for Assignment

Unweighted: via max flow

Build graph: source → workers → jobs → sink. All capacities = 1. Max flow = max matching.

Hopcroft-Karp

Faster bipartite matching: O(E × sqrt(V)). Uses augmenting paths in BFS layers.

Hungarian algorithm

For weighted bipartite matching (assignment). O(V³). Finds min-cost perfect matching.

Real problem

// Assignment: N workers, N jobs, cost[i][j]. Minimize total cost.
// Reduce rows: subtract row min from each row
// Reduce columns similarly
// Cover zeros with min lines
// If lines == n, done. Else adjust and repeat.