This documentation is automatically generated by online-judge-tools/verification-helper
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/general_matching
#include "../../template/template.hpp"
#include "../../graph/flow/gabow-edmonds.hpp"
int main() {
int N, M;
cin >> N >> M;
GabowEdmonds flow(N);
for(int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
flow.add_edge(a, b);
}
auto ret = flow.max_matching();
cout << ret.size() << endl;
for(auto &p : ret) cout << p << endl;
}
#line 1 "test/verify/yosupo-general-matching.test.cpp"
// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/general_matching
#line 1 "template/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
const int64 infll = (1LL << 62) - 1;
const int inf = (1 << 30) - 1;
struct IoSetup {
IoSetup() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
cout << fixed << setprecision(10);
cerr << fixed << setprecision(10);
}
} iosetup;
template <typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
os << p.first << " " << p.second;
return os;
}
template <typename T1, typename T2>
istream &operator>>(istream &is, pair<T1, T2> &p) {
is >> p.first >> p.second;
return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
for (int i = 0; i < (int)v.size(); i++) {
os << v[i] << (i + 1 != v.size() ? " " : "");
}
return os;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
for (T &in : v) is >> in;
return is;
}
template <typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) {
return a < b && (a = b, true);
}
template <typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) {
return a > b && (a = b, true);
}
template <typename T = int64>
vector<T> make_v(size_t a) {
return vector<T>(a);
}
template <typename T, typename... Ts>
auto make_v(size_t a, Ts... ts) {
return vector<decltype(make_v<T>(ts...))>(a, make_v<T>(ts...));
}
template <typename T, typename V>
typename enable_if<is_class<T>::value == 0>::type fill_v(T &t, const V &v) {
t = v;
}
template <typename T, typename V>
typename enable_if<is_class<T>::value != 0>::type fill_v(T &t, const V &v) {
for (auto &e : t) fill_v(e, v);
}
template <typename F>
struct FixPoint : F {
explicit FixPoint(F &&f) : F(forward<F>(f)) {}
template <typename... Args>
decltype(auto) operator()(Args &&...args) const {
return F::operator()(*this, forward<Args>(args)...);
}
};
template <typename F>
inline decltype(auto) MFP(F &&f) {
return FixPoint<F>{forward<F>(f)};
}
#line 4 "test/verify/yosupo-general-matching.test.cpp"
#line 1 "graph/flow/gabow-edmonds.hpp"
// https://qiita.com/Kutimoti_T/items/5b579773e0a24d650bdf
/**
* @brief Gabow Edmonds(一般グラフの最大マッチング)
*
*/
struct GabowEdmonds {
struct edge {
int to, idx;
};
vector<vector<edge> > g;
vector<pair<int, int> > edges;
vector<int> mate, label, first;
queue<int> que;
GabowEdmonds(int n) : g(n + 1), mate(n + 1), label(n + 1, -1), first(n + 1) {}
void add_edge(int u, int v) {
++u, ++v;
g[u].push_back((edge){v, (int)(edges.size() + g.size())});
g[v].push_back((edge){u, (int)(edges.size() + g.size())});
edges.emplace_back(u, v);
}
int find(int x) {
if (label[first[x]] < 0) return first[x];
first[x] = find(first[x]);
return first[x];
}
void rematch(int v, int w) {
int t = mate[v];
mate[v] = w;
if (mate[t] != v) return;
if (label[v] < (int)g.size()) {
mate[t] = label[v];
rematch(label[v], t);
} else {
int x = edges[label[v] - g.size()].first;
int y = edges[label[v] - g.size()].second;
rematch(x, y);
rematch(y, x);
}
}
void assign_label(int x, int y, int num) {
int r = find(x);
int s = find(y);
int join = 0;
if (r == s) return;
label[r] = -num;
label[s] = -num;
while (true) {
if (s != 0) swap(r, s);
r = find(label[mate[r]]);
if (label[r] == -num) {
join = r;
break;
}
label[r] = -num;
}
int v = first[x];
while (v != join) {
que.push(v);
label[v] = num;
first[v] = join;
v = first[label[mate[v]]];
}
v = first[y];
while (v != join) {
que.push(v);
label[v] = num;
first[v] = join;
v = first[label[mate[v]]];
}
}
bool augment_check(int u) {
que = queue<int>();
first[u] = 0;
label[u] = 0;
que.push(u);
while (!que.empty()) {
int x = que.front();
que.pop();
for (auto e : g[x]) {
int y = e.to;
if (mate[y] == 0 && y != u) {
mate[y] = x;
rematch(x, y);
return true;
} else if (label[y] >= 0) {
assign_label(x, y, e.idx);
} else if (label[mate[y]] < 0) {
label[mate[y]] = x;
first[mate[y]] = y;
que.push(mate[y]);
}
}
}
return false;
}
vector<pair<int, int> > max_matching() {
for (int i = 1; i < (int)g.size(); i++) {
if (mate[i] != 0) continue;
if (augment_check(i)) label.assign(g.size(), -1);
}
vector<pair<int, int> > ret;
for (int i = 1; i < (int)g.size(); i++) {
if (i < mate[i]) ret.emplace_back(i - 1, mate[i] - 1);
}
return ret;
}
};
#line 6 "test/verify/yosupo-general-matching.test.cpp"
int main() {
int N, M;
cin >> N >> M;
GabowEdmonds flow(N);
for(int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
flow.add_edge(a, b);
}
auto ret = flow.max_matching();
cout << ret.size() << endl;
for(auto &p : ret) cout << p << endl;
}
Env | Name | Status | Elapsed | Memory |
---|---|---|---|---|
g++ | example_00 | AC | 6 ms | 4 MB |
g++ | example_01 | AC | 6 ms | 4 MB |
g++ | issue610_00 | AC | 6 ms | 4 MB |
g++ | max_random_00 | AC | 8 ms | 4 MB |
g++ | max_random_01 | AC | 14 ms | 6 MB |
g++ | random_00 | AC | 7 ms | 4 MB |
g++ | random_01 | AC | 8 ms | 4 MB |
g++ | sparse_00 | AC | 6 ms | 4 MB |
g++ | sparse_01 | AC | 6 ms | 4 MB |
g++ | sparse_02 | AC | 6 ms | 4 MB |
g++ | sparse_03 | AC | 7 ms | 4 MB |
g++ | sparse_04 | AC | 6 ms | 4 MB |
clang++ | example_00 | AC | 6 ms | 4 MB |
clang++ | example_01 | AC | 6 ms | 4 MB |
clang++ | issue610_00 | AC | 6 ms | 4 MB |
clang++ | max_random_00 | AC | 8 ms | 4 MB |
clang++ | max_random_01 | AC | 14 ms | 6 MB |
clang++ | random_00 | AC | 7 ms | 4 MB |
clang++ | random_01 | AC | 8 ms | 4 MB |
clang++ | sparse_00 | AC | 6 ms | 4 MB |
clang++ | sparse_01 | AC | 6 ms | 4 MB |
clang++ | sparse_02 | AC | 6 ms | 4 MB |
clang++ | sparse_03 | AC | 6 ms | 4 MB |
clang++ | sparse_04 | AC | 6 ms | 4 MB |