-
Notifications
You must be signed in to change notification settings - Fork 1
/
HopcroftCarp.cpp
66 lines (62 loc) · 1.52 KB
/
HopcroftCarp.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#define MAX 100001
#define NIL 0
#define INF (1<<28)
vector< int > G[MAX];
int n, m, match[MAX], dist[MAX];
// n: number of nodes on left side, nodes are numbered 1 to n
// m: number of nodes on right side, nodes are numbered n+1 to n+m
// G = NIL[0] ∪ G1[G[1---n]] ∪ G2[G[n+1---n+m]]
bool bfs() {
int i, u, v, len;
queue< int > Q;
for(i=1; i<=n; i++) {
if(match[i]==NIL) {
dist[i] = 0;
Q.push(i);
}
else dist[i] = INF;
}
dist[NIL] = INF;
while(!Q.empty()) {
u = Q.front(); Q.pop();
if(u!=NIL) {
len = G[u].size();
for(i=0; i<len; i++) {
v = G[u][i];
if(dist[match[v]]==INF) {
dist[match[v]] = dist[u] + 1;
Q.push(match[v]);
}
}
}
}
return (dist[NIL]!=INF);
}
bool dfs(int u) {
int i, v, len;
if(u!=NIL) {
len = G[u].size();
for(i=0; i<len; i++) {
v = G[u][i];
if(dist[match[v]]==dist[u]+1) {
if(dfs(match[v])) {
match[v] = u;
match[u] = v;
return true;
}
}
}
dist[u] = INF;
return false;
}
return true;
}
int hopcroft_karp() {
int matching = 0, i;
// match[] is assumed NIL for all vertex in G
while(bfs())
for(i=1; i<=n; i++)
if(match[i]==NIL && dfs(i))
matching++;
return matching;
}