/
Maximum_Simple_Graph_Matching.cpp
51 lines (51 loc) · 1.6 KB
/
Maximum_Simple_Graph_Matching.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
struct Matching { // 0-base
queue<int> q; int n;
vector<int> fa, s, vis, pre, match;
vector<vector<int>> G;
int Find(int u)
{ return u == fa[u] ? u : fa[u] = Find(fa[u]); }
int LCA(int x, int y) {
static int tk = 0; tk++; x = Find(x); y = Find(y);
for (;; swap(x, y)) if (x != n) {
if (vis[x] == tk) return x;
vis[x] = tk;
x = Find(pre[match[x]]);
}
}
void Blossom(int x, int y, int l) {
for (; Find(x) != l; x = pre[y]) {
pre[x] = y, y = match[x];
if (s[y] == 1) q.push(y), s[y] = 0;
for (int z: {x, y}) if (fa[z] == z) fa[z] = l;
}
}
bool Bfs(int r) {
iota(ALL(fa), 0); fill(ALL(s), -1);
q = queue<int>(); q.push(r); s[r] = 0;
for (; !q.empty(); q.pop()) {
for (int x = q.front(); int u : G[x])
if (s[u] == -1) {
if (pre[u] = x, s[u] = 1, match[u] == n) {
for (int a = u, b = x, last;
b != n; a = last, b = pre[a])
last = match[b], match[b] = a, match[a] = b;
return true;
}
q.push(match[u]); s[match[u]] = 0;
} else if (!s[u] && Find(u) != Find(x)) {
int l = LCA(u, x);
Blossom(x, u, l); Blossom(u, x, l);
}
}
return false;
}
Matching(int _n) : n(_n), fa(n + 1), s(n + 1), vis(n + 1), pre(n + 1, n), match(n + 1, n), G(n) {}
void add_edge(int u, int v)
{ G[u].pb(v), G[v].pb(u); }
int solve() {
int ans = 0;
for (int x = 0; x < n; ++x)
if (match[x] == n) ans += Bfs(x);
return ans;
} // match[x] == n means not matched
};