verify/flows/general-matching/general_matching.test.cpp
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/general_matching"
#include "src/contest/template.hpp"
#include "src/flows/general-matching.hpp"
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
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);
}
cout << gm.max_matching() << "\n";
for(int i=0;i<n;i++){
if(gm.match[i]!=-1&&i<gm.match[i]){
cout << i << " " << gm.match[i] << "\n";
}
}
}
#line 1 "verify/flows/general-matching/general_matching.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/general_matching"
#line 2 "src/contest/template.hpp"
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using db = long double;
using vi = vector<int>;
using vl = vector<ll>;
using vd = vector<db>;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using pdd = pair<db,db>;
const int INF=0x3fffffff;
const ll LINF=0x1fffffffffffffff;
const db DINF=numeric_limits<db>::infinity();
const db EPS=1e-9;
const db PI=acos(db(-1));
template<class T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
#line 2 "src/flows/general-matching.hpp"
/**
* Author: Teetat T.
* Date: 2025-09-03
* Description: General matching using blossom algorithm.
* Time: O(E \sqrt{V} log_{\max(2,1+E/V)}).
*/
struct GeneralMatching{
int n;
vector<vector<int>> adj;
vector<int> match,vis,link,fa,dep;
queue<int> q;
GeneralMatching(int n):n(n),adj(n),match(n,-1),vis(n),link(n),fa(n),dep(n){}
void add_edge(int u,int v){
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
int fp(int u){
while(fa[u]!=u)u=fa[u]=fa[fa[u]];
return u;
}
int lca(int u,int v){
u=fp(u),v=fp(v);
while(u!=v){
if(dep[u]<dep[v])swap(u,v);
u=fp(link[match[u]]);
}
return u;
}
void blossom(int u,int v,int p){
while(fp(u)!=p){
link[u]=v;
v=match[u];
if(vis[v]==0){
vis[v]=1;
q.emplace(v);
}
fa[u]=fa[v]=p;
u=link[v];
}
}
int augment(int u){
while(!q.empty())q.pop();
iota(fa.begin(),fa.end(),0);
fill(vis.begin(),vis.end(),-1);
q.emplace(u);
vis[u]=1;
dep[u]=0;
while(!q.empty()){
int u=q.front();
q.pop();
for(auto v:adj[u]){
if(vis[v]==-1){
vis[v]=0;
link[v]=u;
dep[v]=dep[u]+1;
if(match[v]==-1){
for(int x=v,y=u,z;y!=-1;x=z,y=x==-1?-1:link[x]){
z=match[y];
match[x]=y;
match[y]=x;
}
return 1;
}
vis[match[v]]=1;
dep[match[v]]=dep[u]+2;
q.emplace(match[v]);
}else if(vis[v]==1&&fp(u)!=fp(v)){
int p=lca(u,v);
blossom(u,v,p);
blossom(v,u,p);
}
}
}
return 0;
}
int max_matching(){
int res=0;
for(int u=0;u<n;u++){
if(match[u]!=-1)continue;
for(auto v:adj[u]){
if(match[v]==-1){
match[u]=v;
match[v]=u;
res++;
break;
}
}
}
for(int u=0;u<n;u++){
if(match[u]==-1){
res+=augment(u);
}
}
return res;
}
};
#line 4 "verify/flows/general-matching/general_matching.test.cpp"
int main(){
cin.tie(nullptr)->sync_with_stdio(false);
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);
}
cout << gm.max_matching() << "\n";
for(int i=0;i<n;i++){
if(gm.match[i]!=-1&&i<gm.match[i]){
cout << i << " " << gm.match[i] << "\n";
}
}
}
Back to top page