/** 一般图最大匹配（Graph 带花树算法）【久远】
* 2021-12-24: https://codeforces.com/contest/1615/submission/140509278
**/
struct Graph {
int n;
std::vector<std::vector<int>> e;
Graph(int n) : n(n), e(n) {}
void addEdge(int u, int v) {
e[u].push_back(v);
e[v].push_back(u);
}
std::vector<int> findMatching() {
std::vector<int> match(n, -1), vis(n), link(n), f(n), dep(n);
// disjoint set union
auto find = [&](int u) {
while (f[u] != u)
u = f[u] = f[f[u]];
return u;
};
auto lca = [&](int u, int v) {
u = find(u);
v = find(v);
while (u != v) {
if (dep[u] < dep[v])
std::swap(u, v);
u = find(link[match[u]]);
}
return u;
};
std::queue<int> que;
auto blossom = [&](int u, int v, int p) {
while (find(u) != p) {
link[u] = v;
v = match[u];
if (vis[v] == 0) {
vis[v] = 1;
que.push(v);
}
f[u] = f[v] = p;
u = link[v];
}
};
// find an augmenting path starting from u and augment (if exist)
auto augment = [&](int u) {
while (!que.empty())
que.pop();
std::iota(f.begin(), f.end(), 0);
// vis = 0 corresponds to inner vertices, vis = 1 corresponds to outer vertices
std::fill(vis.begin(), vis.end(), -1);
que.push(u);
vis[u] = 1;
dep[u] = 0;
while (!que.empty()){
int u = que.front();
que.pop();
for (auto v : e[u]) {
if (vis[v] == -1) {
vis[v] = 0;
link[v] = u;
dep[v] = dep[u] + 1;
// found an augmenting path
if (match[v] == -1) {
for (int x = v, y = u, temp; y != -1; x = temp, y = x == -1 ? -1 : link[x]) {
temp = match[y];
match[x] = y;
match[y] = x;
}
return;
}
vis[match[v]] = 1;
dep[match[v]] = dep[u] + 2;
que.push(match[v]);
} else if (vis[v] == 1 && find(v) != find(u)) {
// found a blossom
int p = lca(u, v);
blossom(u, v, p);
blossom(v, u, p);
}
}
}
};
// find a maximal matching greedily (decrease constant)
auto greedy = [&]() {
for (int u = 0; u < n; ++u) {
if (match[u] != -1)
continue;
for (auto v : e[u]) {
if (match[v] == -1) {
match[u] = v;
match[v] = u;
break;
}
}
}
};
greedy();
for (int u = 0; u < n; ++u)
if (match[u] == -1)
augment(u);
return match;
}
};
#line 1 "src/jiangly/graph/04-Graph-Match.hpp"
/** 一般图最大匹配（Graph 带花树算法）【久远】
* 2021-12-24: https://codeforces.com/contest/1615/submission/140509278
**/
struct Graph {
int n;
std::vector<std::vector<int>> e;
Graph(int n) : n(n), e(n) {}
void addEdge(int u, int v) {
e[u].push_back(v);
e[v].push_back(u);
}
std::vector<int> findMatching() {
std::vector<int> match(n, -1), vis(n), link(n), f(n), dep(n);
// disjoint set union
auto find = [&](int u) {
while (f[u] != u)
u = f[u] = f[f[u]];
return u;
};
auto lca = [&](int u, int v) {
u = find(u);
v = find(v);
while (u != v) {
if (dep[u] < dep[v])
std::swap(u, v);
u = find(link[match[u]]);
}
return u;
};
std::queue<int> que;
auto blossom = [&](int u, int v, int p) {
while (find(u) != p) {
link[u] = v;
v = match[u];
if (vis[v] == 0) {
vis[v] = 1;
que.push(v);
}
f[u] = f[v] = p;
u = link[v];
}
};
// find an augmenting path starting from u and augment (if exist)
auto augment = [&](int u) {
while (!que.empty())
que.pop();
std::iota(f.begin(), f.end(), 0);
// vis = 0 corresponds to inner vertices, vis = 1 corresponds to outer vertices
std::fill(vis.begin(), vis.end(), -1);
que.push(u);
vis[u] = 1;
dep[u] = 0;
while (!que.empty()){
int u = que.front();
que.pop();
for (auto v : e[u]) {
if (vis[v] == -1) {
vis[v] = 0;
link[v] = u;
dep[v] = dep[u] + 1;
// found an augmenting path
if (match[v] == -1) {
for (int x = v, y = u, temp; y != -1; x = temp, y = x == -1 ? -1 : link[x]) {
temp = match[y];
match[x] = y;
match[y] = x;
}
return;
}
vis[match[v]] = 1;
dep[match[v]] = dep[u] + 2;
que.push(match[v]);
} else if (vis[v] == 1 && find(v) != find(u)) {
// found a blossom
int p = lca(u, v);
blossom(u, v, p);
blossom(v, u, p);
}
}
}
};
// find a maximal matching greedily (decrease constant)
auto greedy = [&]() {
for (int u = 0; u < n; ++u) {
if (match[u] != -1)
continue;
for (auto v : e[u]) {
if (match[v] == -1) {
match[u] = v;
match[v] = u;
break;
}
}
}
};
greedy();
for (int u = 0; u < n; ++u)
if (match[u] == -1)
augment(u);
return match;
}
};
src/jiangly/graph/04-Graph-Match.hpp