Pattern Guide
Matching via Maximum Flow
"Bipartite matching = max flow in O(E√V). General matching = Blossom algorithm."
Bipartite maximum matching finds the largest set of edges with no shared endpoints. Reduces to max-flow: source → left nodes → right nodes → sink, all edges capacity 1. Hopcroft-Karp finds augmenting paths in batches (BFS layers + DFS), achieving O(E√V). König's theorem: max matching = min vertex cover in bipartite graphs. Covers: assignment problems, independent set, and edge coloring.
Problems you can solve with this pattern
4 problems · click any to start solving
class BipartiteMatching {
constructor(L, R) {
this.L = L; this.R = R;
this.adj = Array.from({length: L}, () => []);
this.matchL = new Array(L).fill(-1);
this.matchR = new Array(R).fill(-1);
}
addEdge(u, v) { this.adj[u].push(v); }
// Hopcroft-Karp: O(E√V)
maxMatching() {
let matching = 0;
while (this._bfs()) {
for (let u = 0; u < this.L; u++)
if (this.matchL[u] === -1 && this._dfs(u)) matching++;
}
return matching;
}
_bfs() {
this.dist = new Array(this.L).fill(Infinity);
const queue = [];
for (let u = 0; u < this.L; u++) {
if (this.matchL[u] === -1) { this.dist[u] = 0; queue.push(u); }
}
let found = false;
let i = 0;
while (i < queue.length) {
const u = queue[i++];
for (const v of this.adj[u]) {
const w = this.matchR[v];
if (w === -1) found = true;
else if (this.dist[w] === Infinity) {
this.dist[w] = this.dist[u] + 1;
queue.push(w);
}
}
}
return found;
}
_dfs(u) {
for (const v of this.adj[u]) {
const w = this.matchR[v];
if (w === -1 || (this.dist[w] === this.dist[u] + 1 && this._dfs(w))) {
this.matchL[u] = v; this.matchR[v] = u;
return true;
}
}
this.dist[u] = Infinity;
return false;
}
}Bipartite matching: find max set of edges with no shared endpoint. Flow model: all edges capacity 1. Augmenting path: path from unmatched left to unmatched right through alternating matched/unmatched edges. Hopcroft-Karp: BFS to find shortest augmenting paths (all same length), DFS to find vertex-disjoint augmenting paths simultaneously. Each phase increases matching by at least 1, and there are O(√V) phases.
class BipartiteMatching {
constructor(L, R) {
this.L = L; this.R = R;
this.adj = Array.from({length: L}, () => []);
this.matchL = new Array(L).fill(-1);
this.matchR = new Array(R).fill(-1);
}
addEdge(u, v) { this.adj[u].push(v); }
// Hopcroft-Karp: O(E√V)
maxMatching() {
let matching = 0;
while (this._bfs()) {
for (let u = 0; u < this.L; u++)
if (this.matchL[u] === -1 && this._dfs(u)) matching++;
}
return matching;
}
_bfs() {
this.dist = new Array(this.L).fill(Infinity);
const queue = [];
for (let u = 0; u < this.L; u++) {
if (this.matchL[u] === -1) { this.dist[u] = 0; queue.push(u); }
}
let found = false;
let i = 0;
while (i < queue.length) {
const u = queue[i++];
for (const v of this.adj[u]) {
const w = this.matchR[v];
if (w === -1) found = true;
else if (this.dist[w] === Infinity) {
this.dist[w] = this.dist[u] + 1;
queue.push(w);
}
}
}
return found;
}
_dfs(u) {
for (const v of this.adj[u]) {
const w = this.matchR[v];
if (w === -1 || (this.dist[w] === this.dist[u] + 1 && this._dfs(w))) {
this.matchL[u] = v; this.matchR[v] = u;
return true;
}
}
this.dist[u] = Infinity;
return false;
}
}- Max matching = min vertex cover
- Max independent set = n - max matching
Algorithm selection:
- Simple bipartite matching (n ≤ 500): Hungarian/Augmenting paths O(V × E)
- Faster matching (large n): Hopcroft-Karp O(E√V)
- General (non-bipartite) matching: Blossom algorithm O(V³)
Flow reduction: Source → left nodes (cap 1) → right nodes (cap 1) → sink (cap 1). Max flow = max matching. Min cut = min vertex cover (by König's).