sotanishy's competitive programming library
sotanishy's code snippets for competitive programming
test/yosupo/general_matching.test.cpp
- View this file on GitHub
- Last update: 2024-01-08 13:32:33+09:00
- Problem: https://judge.yosupo.jp/problem/general_matching
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/general_matching"
#include "../../graph/general_matching.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
GeneralMatching gm(N);
for (int i = 0; i < M; ++i) {
int u, v;
cin >> u >> v;
gm.add_edge(u, v);
}
auto ans = gm.max_matching();
cout << ans.size() << "\n";
for (auto [a, b] : ans) {
cout << a << " " << b << "\n";
}
}#line 1 "test/yosupo/general_matching.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/general_matching"
#line 2 "graph/general_matching.hpp"
#include <algorithm>
#include <cassert>
#include <queue>
#include <vector>
class GeneralMatching {
public:
GeneralMatching() = default;
explicit GeneralMatching(int n)
: n(n), m(n + n / 2), G(m, std::vector<bool>(m)), mate(m, -1) {}
void add_edge(int u, int v) { G[u][v] = G[v][u] = true; }
std::vector<std::pair<int, int>> max_matching() {
// par: parent in the alternating forest
// dep: 0 if even, 1 if odd, -1 if not in the forest
// comp: id of the comp in the forest
// alive: whether the blossom/vertex is alive
// blossom: members of the blossom
std::vector<int> par(m), dep(m), comp(m);
std::vector<bool> alive(m, true);
std::vector<std::vector<int>> blossom(m);
auto get_ancestors = [&](int v) {
std::vector<int> ret;
while (v != -1) {
ret.push_back(v);
v = par[v];
}
return ret;
};
auto flip_to_root = [&](int v) {
mate[v] = -1;
int w = par[v];
while (w != -1) {
int p = par[w];
mate[w] = p;
mate[p] = w;
w = par[p];
}
};
for (int ans = 0;; ++ans) {
std::ranges::fill(par, -1);
std::ranges::fill(dep, -1);
std::ranges::fill(comp, -1);
bool augment = false;
int c = n; // n + number of blossoms
// seed
std::queue<int> que;
for (int v = 0; v < n; ++v) {
if (mate[v] == -1) {
que.push(v);
dep[v] = 0;
comp[v] = v;
}
}
// repeat until an augmenting path is found
while (!que.empty() && !augment) {
int v = que.front();
que.pop();
if (!alive[v]) continue;
for (int u = 0; u < c; ++u) {
if (!G[v][u] || !alive[u] || dep[u] == 1) continue;
if (dep[u] == -1) {
// grow
int w = mate[u];
par[u] = v;
par[w] = u;
dep[u] = 1;
dep[w] = 0;
comp[u] = comp[w] = comp[v];
que.push(w);
} else if (comp[v] == comp[u]) {
// shrink
// build the blossom
auto av = get_ancestors(v);
auto au = get_ancestors(u);
int w; // lca
while (!av.empty() && !au.empty() &&
av.back() == au.back()) {
w = av.back();
av.pop_back();
au.pop_back();
}
blossom[c] = std::move(av);
blossom[c].push_back(w);
std::ranges::reverse(blossom[c]);
std::ranges::move(au, std::back_inserter(blossom[c]));
// contract
if (par[w] != -1) mate[par[w]] = c;
par[c] = mate[c] = par[w];
dep[c] = 0;
comp[c] = comp[w];
for (int x : blossom[c]) {
alive[x] = false;
mate[x] = -1;
}
for (int x : blossom[c]) {
for (int y = 0; y < c; ++y) {
if (G[x][y] && alive[y]) {
G[y][c] = G[c][y] = true;
if (par[y] == x) par[y] = c;
}
}
}
que.push(c);
++c;
break;
} else {
// augment
augment = true;
flip_to_root(v);
flip_to_root(u);
mate[v] = u;
mate[u] = v;
break;
}
}
}
// restore blossoms
while (c > n) {
--c;
int b = blossom[c].size();
// select the base
int base_idx;
if (mate[c] == -1) {
base_idx = 0;
} else {
base_idx = -1;
for (int i = 0; i < b; ++i) {
int x = blossom[c][i];
int y = mate[c];
if (G[x][y]) {
base_idx = i;
mate[c] = -1;
mate[y] = x;
mate[x] = y;
break;
}
}
assert(base_idx != -1);
}
// restore matches
for (int i = 1; i < b; i += 2) {
int u = blossom[c][(base_idx + i) % b];
int v = blossom[c][(base_idx + i + 1) % b];
mate[u] = v;
mate[v] = u;
}
for (int x : blossom[c]) alive[x] = true;
for (int y = 0; y < c; ++y) G[c][y] = G[y][c] = false;
blossom[c].clear();
}
if (!augment) {
std::vector<std::pair<int, int>> matches;
for (int i = 0; i < n; ++i) {
if (i < mate[i]) {
matches.emplace_back(i, mate[i]);
}
}
return matches;
}
}
}
private:
int n, m; // m: maximum number of vertices + blossoms
std::vector<std::vector<bool>> G; // adjacency matrix
std::vector<int> mate; // -1 if not matched
};
#line 4 "test/yosupo/general_matching.test.cpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N, M;
cin >> N >> M;
GeneralMatching gm(N);
for (int i = 0; i < M; ++i) {
int u, v;
cin >> u >> v;
gm.add_edge(u, v);
}
auto ans = gm.max_matching();
cout << ans.size() << "\n";
for (auto [a, b] : ans) {
cout << a << " " << b << "\n";
}
}