Bipartite Matching

A bipartite matching chooses compatibility edges between two separate groups so no vertex is used twice. Think of workers and jobs or students and projects: an edge means an acceptable pairing, and the goal is the largest number of pairs. Kuhn’s DFS-based algorithm is short and exposes the central idea of alternating paths. It solves unweighted maximum cardinality matching, not the minimum-cost weighted assignment problem solved by the Hungarian algorithm.

Prerequisites: Depth-first search; alternating paths from Introduction to Network Flow. Difficulty: Advanced. Review: Depth-first search, Introduction to Network Flow.

Build the idea

1. 1. Separate the two sides

   Number left vertices 1..L and right vertices 1..R independently. Store only left→right compatibility lists. owner[v] is the left vertex currently using right vertex v, or zero when v is free. Although both sides may contain a vertex numbered 1, they are different objects. A matching size is a count of pairs; it is not a sum of edge weights.

2. 2. Make room by moving an existing match

   To match left vertex u, try each compatible v. If v is free, use it immediately. If v is occupied by w, recursively try to move w elsewhere. On success, assign v to u. The recursion traces unmatched left→right edges and matched right→left steps. Flipping every chosen edge increases cardinality by one, while each internal vertex still participates in exactly one pair.

3. 3. Trace a reassignment

   With edges 1→{1,2}, 2→{1,3}, 3→{2}, the first search matches left 1 to right 1. Searching from left 2 can move left 1 to right 2 and give right 1 to left 2. Searching from left 3 can then move left 1 back through right 1, move left 2 to right 3, and take right 2. Final matching size is 3. A greedy “take a free neighbor or give up” would miss such repair paths.

4. 4. Prevent loops and justify optimality

   seen[left] marks vertices during ONE augmentation attempt. Alternating paths can revisit a left vertex through different occupied neighbors, so this mark prevents cycles. Reset it for each new root: a failed search under an earlier matching must not forbid a route after reassignment. The symmetric difference between a larger matching and the current one would contain an alternating path with one more new edge than old edge. Thus no augmenting path implies maximum cardinality. Processing each new left vertex maintains a maximum matching for the processed prefix.

5. 5. Read the compact implementation

   A recursive call succeeds before owner[v] is overwritten, so unsuccessful branches leave the matching unchanged. Each left vertex starts unmatched when first processed; recursive reassignments keep earlier successful roots matched. The sample prints only the cardinality, allowing different correct pairings. To print pairs, scan owner[v] after all searches; every nonzero entry gives one pair.

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

#include<iostream>
#include<vector>
using namespace std;
vector<vector<int>>graph;
vector<int>owner;
vector<char>seen;
bool augment(int left){
    if(seen[left]){
        return false;
    }
    seen[left]=true;
    for(int right:graph[left]){
        if(owner[right]==0||augment(owner[right])){
            owner[right]=left; // Reassign only after a whole augmenting path succeeds.
            return true;
        }
    }
    return false;
}
int main(){
    int L,R,m;
    if(!(cin>>L>>R>>m)){
        return 0;
    }
    graph.resize(L+1);
    owner.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;
    for(int u=1;u<=L;++u){
        seen.assign(L+1,false); // Fresh visited set for this attempt.
        if(augment(u)){
            ++answer;
        }
    }
    cout<<answer<<'\n';
}

Complexity analysis

O(L(V+E)) is a conservative bound including clearing the L-element visited array for each root. In the usual edge-dominated bipartite graph this is stated O(LE); more precisely this program uses O(L²+LE+R) including initialization. Each search visits a left vertex once and scans its list once. O(L+R+E) memory and O(L) recursion depth. Using timestamps can remove repeated visited-array clearing.

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

All three left vertices can be paired: (1,1), (2,3), (3,2). The algorithm may find another maximum arrangement.

Practical applications

Choose Kuhn for small or moderate unweighted bipartite instances and easy matching reductions. Put the smaller side on the DFS side when possible. Use Hopcroft–Karp for larger sparse graphs, Hungarian for dense weighted perfect assignment, and general max flow when pair edges have capacities beyond one.

Check your understanding

Why may we recursively search from the current owner of a right vertex?

Put it into practice

Print the final pairs and test a case where a greedy first pairing blocks another vertex.