Bipartite Matching - Hopcroft-Karp

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct HopcroftKarp {
5
    // Left side size nL, Right side size nR
6
    int nL, nR;
7
    vector<vector<int>> adj; // adj[u] = list of v in R that u in L connects to
8
    vector<int> dist;        // distance (level) for BFS on L side
9
    vector<int> matchL;      // matchL[u] = matched v in R or -1
10
    vector<int> matchR;      // matchR[v] = matched u in L or -1
11
12
    HopcroftKarp(int nL, int nR): nL(nL), nR(nR) {
13
        adj.assign(nL, {});
14
        matchL.assign(nL, -1);
15
        matchR.assign(nR, -1);
16
        dist.resize(nL);
17
    }
18
19
    void add_edge(int u, int v) {
20
        // 0-based: u in [0,nL), v in [0,nR)
21
        adj[u].push_back(v);
22
    }
23
24
    bool bfs() {
25
        queue<int> q;
26
        // Initialize distances for free L-vertices
27
        for (int u = 0; u < nL; ++u) {
28
            if (matchL[u] == -1) { dist[u] = 0; q.push(u); }
29
            else dist[u] = -1; // -1 means unvisited in this BFS
30
        }
31
        bool reachableFreeR = false;
32
        while (!q.empty()) {
33
            int u = q.front(); q.pop();
34
            for (int v : adj[u]) {
35
                int mu = matchR[v]; // matched partner of v on L side (or -1)
36
                // We can go L(u)->R(v) if edge is unmatched (always true in L->R direction)
37
                // and then R(v)->L(mu) via matched edge if exists.
38
                if (mu != -1) {
39
                    if (dist[mu] == -1) { // not yet layered
40
                        dist[mu] = dist[u] + 1;
41
                        q.push(mu);
42
                    }
43
                } else {
44
                    // Found an unmatched R at some level; indicates there is a shortest augmenting path
45
                    reachableFreeR = true;
46
                }
47
            }
48
        }
49
        return reachableFreeR;
50
    }
51
52
    bool dfs(int u, vector<int>& it) {
53
        for (int& i = it[u]; i < (int)adj[u].size(); ++i) {
54
            int v = adj[u][i];
55
            int mu = matchR[v];
56
            if (mu == -1) {
57
                // We reached a free R-vertex along a shortest path layer; augment here
58
                matchL[u] = v;
59
                matchR[v] = u;
60
                return true;
61
            } else if (dist[mu] == dist[u] + 1 && dfs(mu, it)) {
62
                // Follow layer-respecting alternating edge R(v)->L(mu)
63
                matchL[u] = v;
64
                matchR[v] = u;
65
                return true;
66
            }
67
        }
68
        // Dead end; do not revisit u in this phase
69
        dist[u] = -1;
70
        return false;
71
    }
72
73
    int max_matching() {
74
        int matching = 0;
75
        // While there exists some shortest augmenting path
76
        while (bfs()) {
77
            // Iteration pointers to avoid re-scanning edges from L
78
            vector<int> it(nL, 0);
79
            for (int u = 0; u < nL; ++u) {
80
                if (matchL[u] == -1) {
81
                    if (dfs(u, it)) matching++;
82
                }
83
            }
84
        }
85
        return matching;
86
    }
87
};
88
89
int main() {
90
    ios::sync_with_stdio(false);
91
    cin.tie(nullptr);
92
93
    // Example: 4 workers (L) and 4 jobs (R)
94
    int nL = 4, nR = 4;
95
    HopcroftKarp hk(nL, nR);
96
    // Edges (0-based): compatible worker->job
97
    hk.add_edge(0, 0);
98
    hk.add_edge(0, 1);
99
    hk.add_edge(1, 1);
100
    hk.add_edge(1, 2);
101
    hk.add_edge(2, 2);
102
    hk.add_edge(3, 2);
103
    hk.add_edge(3, 3);
104
105
    int m = hk.max_matching();
106
    cout << "Maximum matching size = " << m \<< "\n";
107
108
    // Print pairs u-L matched with v-R
109
    for (int u = 0; u < nL; ++u) if (hk.matchL[u] != -1) {
110
        cout << "L(" << u << ") - R(" << hk.matchL[u] << ")\n";
111
    }
112
113
    return 0;
114
}
115

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct HopcroftKarp {
5
    int nL, nR; vector<vector<int>> adj; vector<int> dist, matchL, matchR;
6
    HopcroftKarp(int nL, int nR): nL(nL), nR(nR) {
7
        adj.assign(nL, {}); matchL.assign(nL, -1); matchR.assign(nR, -1); dist.resize(nL);
8
    }
9
    void add_edge(int u, int v){ adj[u].push_back(v);}    
10
    bool bfs(){
11
        queue<int> q; bool reachable=false;
12
        for(int u=0;u<nL;++u){ if(matchL[u]==-1){dist[u]=0;q.push(u);} else dist[u]=-1; }
13
        while(!q.empty()){
14
            int u=q.front(); q.pop();
15
            for(int v: adj[u]){
16
                int mu=matchR[v];
17
                if(mu!=-1){ if(dist[mu]==-1){ dist[mu]=dist[u]+1; q.push(mu);} }
18
                else reachable=true;
19
            }
20
        }
21
        return reachable;
22
    }
23
    bool dfs(int u, vector<int>& it){
24
        for(int &i=it[u]; i<(int)adj[u].size(); ++i){
25
            int v=adj[u][i]; int mu=matchR[v];
26
            if(mu==-1 || (dist[mu]==dist[u]+1 && dfs(mu,it))){ matchL[u]=v; matchR[v]=u; return true; }
27
        }
28
        dist[u]=-1; return false;
29
    }
30
    int max_matching(){ int ans=0; while(bfs()){ vector<int> it(nL); for(int u=0;u<nL;++u) if(matchL[u]==-1 && dfs(u,it)) ++ans; } return ans; }
31
};
32
33
// Compute a minimum vertex cover from maximum matching in a bipartite graph.
34
// Returns pair<coverL, coverR> as boolean arrays marking which vertices are in the MVC.
35
// Procedure: Run alternating BFS from all free L-vertices using unmatched edges L->R and matched edges R->L.
36
// Let VisL, VisR be visited sets. Then MVC = (L \ VisL) union (R ∩ VisR).
37
38
pair<vector<char>, vector<char>> min_vertex_cover(const HopcroftKarp& hk){
39
    int nL=hk.nL, nR=hk.nR;
40
    vector<char> visL(nL,0), visR(nR,0);
41
    queue<int> q;
42
    // Start from all free vertices in L
43
    for(int u=0;u<nL;++u) if(hk.matchL[u]==-1){ visL[u]=1; q.push(u);}    
44
    while(!q.empty()){
45
        int u=q.front(); q.pop();
46
        // Traverse unmatched edges L->R
47
        for(int v: hk.adj[u]){
48
            if(hk.matchL[u]==v) continue; // skip matched edge u-v here (we only want unmatched L->R)
49
            if(!visR[v]){
50
                visR[v]=1; // visit R via unmatched edge
51
                int mu = hk.matchR[v];
52
                if(mu!=-1 && !visL[mu]){ visL[mu]=1; q.push(mu);} // follow matched edge R->L
53
            }
54
        }
55
    }
56
    // Build MVC sets
57
    vector<char> coverL(nL,0), coverR(nR,0);
58
    for(int u=0;u<nL;++u) if(!visL[u]) coverL[u]=1;     // L \ VisL
59
    for(int v=0;v<nR;++v) if(visR[v])  coverR[v]=1;     // R ∩ VisR
60
    return {coverL, coverR};
61
}
62
63
int main(){
64
    ios::sync_with_stdio(false); cin.tie(nullptr);
65
66
    // Example graph
67
    int nL=3, nR=3; HopcroftKarp hk(nL,nR);
68
    hk.add_edge(0,0); hk.add_edge(0,1);
69
    hk.add_edge(1,1);
70
    hk.add_edge(2,1); hk.add_edge(2,2);
71
72
    int mm = hk.max_matching();
73
    cout << "Max matching = " << mm << "\n";
74
75
    auto [covL, covR] = min_vertex_cover(hk);
76
    cout << "Min Vertex Cover (L side indices): ";
77
    for(int u=0;u<nL;++u) if(covL[u]) cout << u << ' '; cout << "\n";
78
    cout << "Min Vertex Cover (R side indices): ";
79
    for(int v=0;v<nR;++v) if(covR[v]) cout << v << ' '; cout << "\n";
80
81
    // You can also compute maximum independent set in bipartite graphs as V - MVC
82
    int mvc = accumulate(covL.begin(), covL.end(), 0) + accumulate(covR.begin(), covR.end(), 0);
83
    cout << "|MVC| = " << mvc << ", |Max Independent Set| = " << (nL+nR - mvc) << "\n";
84
    return 0;
85
}
86

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Color a general undirected graph to test bipartiteness and build L/R partitions.
5
// Then connect edges from L to R accordingly and run Hopcroft–Karp.
6
7
struct HopcroftKarp {
8
    int nL, nR; vector<vector<int>> adj; vector<int> dist, matchL, matchR;
9
    HopcroftKarp(int nL, int nR): nL(nL), nR(nR) {
10
        adj.assign(nL, {}); matchL.assign(nL, -1); matchR.assign(nR, -1); dist.resize(nL);
11
    }
12
    void add_edge(int u, int v){ adj[u].push_back(v);}    
13
    bool bfs(){ queue<int> q; bool ok=false; for(int u=0;u<nL;++u){ if(matchL[u]==-1){dist[u]=0;q.push(u);} else dist[u]=-1; }
14
        while(!q.empty()){ int u=q.front(); q.pop(); for(int v: adj[u]){ int mu=matchR[v]; if(mu!=-1){ if(dist[mu]==-1){ dist[mu]=dist[u]+1; q.push(mu);} } else ok=true; } } return ok; }
15
    bool dfs(int u, vector<int>& it){ for(int &i=it[u]; i<(int)adj[u].size(); ++i){ int v=adj[u][i]; int mu=matchR[v]; if(mu==-1 || (dist[mu]==dist[u]+1 && dfs(mu,it))){ matchL[u]=v; matchR[v]=u; return true; } } dist[u]=-1; return false; }
16
    int max_matching(){ int ans=0; while(bfs()){ vector<int> it(nL); for(int u=0;u<nL;++u) if(matchL[u]==-1 && dfs(u,it)) ++ans; } return ans; }
17
};
18
19
int main(){
20
    ios::sync_with_stdio(false); cin.tie(nullptr);
21
22
    int n, m; // general undirected graph
23
    // Example input: n m then m edges 0-based
24
    // 4 4
25
    // 0 1
26
    // 1 2
27
    // 2 3
28
    // 0 3
29
    cin >> n >> m;
30
    vector<vector<int>> g(n);
31
    for(int i=0;i<m;++i){ int u,v; cin>>u>>v; g[u].push_back(v); g[v].push_back(u);}    
32
33
    // BFS color to test bipartiteness
34
    const int UNK=-1; vector<int> color(n, UNK);
35
    queue<int> q;
36
    bool bip=true; vector<int> Lmap(n,-1), Rmap(n,-1); int nL=0, nR=0;
37
    for(int s=0;s<n;++s){ if(color[s]!=UNK) continue; color[s]=0; q.push(s);
38
        while(!q.empty() && bip){ int u=q.front(); q.pop(); for(int v: g[u]){ if(color[v]==UNK){ color[v]=color[u]^1; q.push(v);} else if(color[v]==color[u]){ bip=false; break; } } }
39
    }
40
    if(!bip){ cout << "Graph is not bipartite.\n"; return 0; }
41
42
    // Build indices for L and R partitions
43
    for(int i=0;i<n;++i){ if(color[i]==0) Lmap[i]=nL++; else Rmap[i]=nR++; }
44
    HopcroftKarp hk(nL, nR);
45
    for(int u=0;u<n;++u){ if(color[u]!=0) continue; // only add L->R edges once
46
        for(int v: g[u]) if(color[v]==1){ hk.add_edge(Lmap[u], Rmap[v]); }
47
    }
48
49
    cout << "Maximum matching = " << hk.max_matching() << "\n";
50
    for(int u=0;u<nL;++u) if(hk.matchL[u]!=-1){ cout << "L("<<u<<") - R("<<hk.matchL[u]<<")\n"; }
51
52
    return 0;
53
}
54

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Reduce DAG minimum path cover (vertex-disjoint) to bipartite matching.
5
// Build bipartite graph with left and right copies of each vertex.
6
// For each edge u->v in DAG, add L(u) -> R(v). Then MinPathCover = n - MaxMatching.
7
8
struct HopcroftKarp {
9
    int nL, nR; vector<vector<int>> adj; vector<int> dist, matchL, matchR;
10
    HopcroftKarp(int nL, int nR): nL(nL), nR(nR){ adj.assign(nL,{}); matchL.assign(nL,-1); matchR.assign(nR,-1); dist.resize(nL);}    
11
    void add_edge(int u,int v){ adj[u].push_back(v);}    
12
    bool bfs(){ queue<int> q; bool ok=false; for(int u=0;u<nL;++u){ if(matchL[u]==-1){dist[u]=0;q.push(u);} else dist[u]=-1; }
13
        while(!q.empty()){ int u=q.front(); q.pop(); for(int v: adj[u]){ int mu=matchR[v]; if(mu!=-1){ if(dist[mu]==-1){ dist[mu]=dist[u]+1; q.push(mu);} } else ok=true; } } return ok; }
14
    bool dfs(int u, vector<int>& it){ for(int &i=it[u]; i<(int)adj[u].size(); ++i){ int v=adj[u][i]; int mu=matchR[v]; if(mu==-1 || (dist[mu]==dist[u]+1 && dfs(mu,it))){ matchL[u]=v; matchR[v]=u; return true; } } dist[u]=-1; return false; }
15
    int max_matching(){ int ans=0; while(bfs()){ vector<int> it(nL); for(int u=0;u<nL;++u) if(matchL[u]==-1 && dfs(u,it)) ++ans; } return ans; }
16
};
17
18
int main(){
19
    ios::sync_with_stdio(false); cin.tie(nullptr);
20
21
    int n, m; // DAG with vertices 0..n-1 and m directed edges
22
    // Example:
23
    // 5 5
24
    // 0 1
25
    // 0 2
26
    // 1 3
27
    // 2 3
28
    // 3 4
29
    cin >> n >> m;
30
    vector<vector<int>> dag(n);
31
    for(int i=0;i<m;++i){ int u,v; cin>>u>>v; dag[u].push_back(v);}    
32
33
    // Build bipartite graph L(0..n-1) -> R(0..n-1)
34
    HopcroftKarp hk(n, n);
35
    for(int u=0; u<n; ++u) for(int v: dag[u]) hk.add_edge(u, v);
36
37
    int mm = hk.max_matching();
38
    int minPathCover = n - mm;
39
    cout << "Maximum matching = " << mm << "\n";
40
    cout << "Minimum path cover in DAG = " << minPathCover << "\n";
41
42
    // Optionally reconstruct the paths:
43
    // For each vertex u, out-match to v if matchL[u]==v; build chains starting at vertices with no in-match (matchR[u]==-1).
44
    vector<int> outMatch(n, -1), inMatch(n, -1);
45
    for(int u=0; u<n; ++u) if(hk.matchL[u]!=-1) outMatch[u]=hk.matchL[u];
46
    for(int v=0; v<n; ++v) if(hk.matchR[v]!=-1) inMatch[v]=hk.matchR[v];
47
48
    vector<char> used(n, 0);
49
    for(int u=0; u<n; ++u){
50
        if(inMatch[u]==-1){ // start of a path
51
            int x=u; vector<int> path;
52
            while(x!=-1 && !used[x]){ used[x]=1; path.push_back(x); x=outMatch[x]; }
53
            if(!path.empty()){
54
                cout << "Path: ";
55
                for(size_t i=0;i<path.size();++i){ cout<<path[i]<<(i+1==path.size()? '\n':' ');}            
56
            }
57
        }
58
    }
59
60
    return 0;
61
}
62