Hopcroft–Karp Algorithm

Hopcroft–Karp finds a maximum cardinality bipartite matching by augmenting along many shortest alternating paths in each phase. It combines the reassignment idea of Kuhn with BFS layers similar to Dinic. It is especially useful for large sparse compatibility graphs where one DFS search per new pair would be too slow. Both sides remain unweighted: costs and assignment preferences require a different objective.

Prerequisites: Bipartite Matching; BFS layering; residual paths. Difficulty: Advanced. Review: Bipartite Matching.

Build the idea

1. 1. Keep both matching directions

   leftMate[u] is u’s current right partner and rightMate[v] its left partner; zero means unmatched. BFS starts simultaneously from every unmatched left vertex. A step from a left vertex follows a compatibility edge to a right vertex, then, if that right vertex is occupied, its matched edge back to another left vertex. dist[] counts these left-side stages, not ordinary vertex distance.

2. 2. Stop at the shortest free-right layer

   When BFS finds an unmatched right vertex next to u, record shortest = dist[u]+1. Continue enough BFS to discover all shortest augmenting possibilities, but do not extend vertices at or beyond shortest. This restriction matters: arbitrary-length DFS augmentations would lose the phase analysis. A matched neighbor’s owner enters the next left-side layer only once.

3. 3. Augment only through valid layers

   DFS from each free left root may finish at a free right vertex only if dist[u]+1 equals shortest. If the neighbor is occupied, recurse only to an owner exactly one layer deeper. Current-edge pointers avoid rescanning adjacency entries in the phase. An exhausted vertex receives infinite distance. Successful recursion flips the alternating path and updates BOTH mate arrays, keeping the matching consistent.

4. 4. Trace batching on the sample

   Initially every left vertex is free, so all shortest paths have a single compatibility edge. A phase may match 1→1, 2→3, 3→2 immediately. If edge order produces only two pairs in that phase, another BFS discovers a longer shortest alternating path and repairs the matching. The exact number of phases can depend on choices; the maximum cardinality is always 3. Unlike Kuhn, the goal is a maximal collection of compatible shortest augmentations in each fixed layering.

5. 5. Explain the square-root bound

   After a phase blocks all shortest augmenting paths, the shortest length increases. There can be only O(√V) phases with length at most √V. Afterwards compare the current matching with an optimal one: their symmetric difference contains vertex-disjoint augmenting paths, each now longer than √V. Only O(√V) such paths can fit among V vertices, so at most that many further augmentations, hence phases, remain. Each phase scans O(V+E) data with pointers. This gives O((V+E)√V), commonly O(E√V) after ignoring isolated vertices.

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
vector<vector<int>>graph;
vector<int>leftMate,rightMate,dist,nextEdge;
int shortest;
bool layers(int L){
    const int INF=1000000000;
    dist.assign(L+1,INF);
    queue<int>q;
    shortest=INF;
    for(int u=1;u<=L;++u){
        if(leftMate[u]==0){
            dist[u]=0;
            q.push(u);
        }
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        if(dist[u]>=shortest){
            continue;
        }
        for(int v:graph[u]){
            int w=rightMate[v];
            if(w==0){
                shortest=min(shortest,dist[u]+1);
            }
            else if(dist[w]==INF){
                dist[w]=dist[u]+1;
                q.push(w);
            }
        }
    }
    return shortest!=INF;
}
bool augment(int u){
    for(int&i=nextEdge[u];i<(int)graph[u].size();++i){
        int v=graph[u][i],w=rightMate[v];
        bool usable=w==0?dist[u]+1==shortest:dist[w]==dist[u]+1&&augment(w);
        if(usable){
            leftMate[u]=v;
            rightMate[v]=u;
            return true;
        }
    }
    dist[u]=1000000000; // No remaining layered augmenting suffix.
    return false;
}
int main(){
    int L,R,m;
    if(!(cin>>L>>R>>m)){
        return 0;
    }
    graph.resize(L+1);
    leftMate.assign(L+1,0);
    rightMate.assign(R+1,0);
    for(int i=0;i<m;++i){
        int u,v;
        cin>>u>>v;
        graph[u].push_back(v);
    }
    int answer=0;
    while(layers(L)){
        nextEdge.assign(L+1,0);
        for(int u=1;u<=L;++u){
            if(leftMate[u]==0&&augment(u)){
                ++answer;
            }
        }
    }
    cout<<answer<<'\n';
}

Complexity analysis

Let V=L+R. O((V+E)√V) time including vertex scans; conventionally O(E√V) for the relevant nonisolated graph. BFS and all DFS searches in a phase total O(V+E), and there are O(√V) phases. O(V+E) space includes mates, levels, pointers, queue and recursive stack.

Example input and output

Read L R m, then m compatible pairs u v, with u in 1..L and v in 1..R. The sides have separate numbering. L,R≥1. Output the maximum number of disjoint pairs.

Input

3 3 5
1 1
1 2
2 1
2 3
3 2

Output

3

A perfect matching exists: left 1 with right 1, left 2 with right 3, and left 3 with right 2.

Practical applications

Use for large worker/job or compatibility matching, vertex-disjoint alternating structures and bipartite reductions. Kuhn is simpler on tiny graphs. Dinic on the unit flow reduction reaches a similar special-case bound, but Hopcroft–Karp stores less generic flow machinery. Weighted perfect assignment calls for Hungarian.

Check your understanding

What must DFS preserve during one Hopcroft–Karp phase?

Put it into practice

Compare phase counts with Kuhn’s root attempts on random sparse bipartite inputs.