verify/flows/hopcroft-karp/bipartitematching.test.cpp

• View this file on GitHub
• Last update: 2025-07-19 14:29:34+09:00
• Problem: https://judge.yosupo.jp/problem/bipartitematching

Depends on

• src/contest/template.hpp
• src/flows/hopcroft-karp.hpp

Code

#define PROBLEM "https://judge.yosupo.jp/problem/bipartitematching"
#include "src/contest/template.hpp"
#include "src/flows/hopcroft-karp.hpp"

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m,e;
    cin >> n >> m >> e;
    HopcroftKarp bm(n,m);
    for(int i=0;i<e;i++){
        int u,v;
        cin >> u >> v;
        bm.add_edge(u,v);
    }
    cout << bm.max_matching() << "\n";
    for(int i=0;i<n;i++){
        if(bm.match[i]!=-1){
            cout << i << " " << bm.match[i]-n << "\n";
        }
    }
}

#line 1 "verify/flows/hopcroft-karp/bipartitematching.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/bipartitematching"
#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/hopcroft-karp.hpp"

/**
 * Author: Teetat T.
 * Date: 2024-03-31
 * Description: Fast bipartite matching algorithm.
 * Time: $O(E\sqrt{V})$
 */

struct HopcroftKarp{
    int n,m;
    vector<int> match,lv,ptr;
    vector<vector<int>> adj;
    HopcroftKarp(){}
    HopcroftKarp(int _n,int _m){init(_n,_m);}
    void init(int _n,int _m){
        n=_n,m=_m;
        adj.assign(n+m,vector<int>{});
    }
    void add_edge(int u,int v){
        adj[u].emplace_back(v+n);
    }
    void bfs(){
        lv.assign(n,-1);
        queue<int> q;
        for(int i=0;i<n;i++)if(match[i]==-1){
            lv[i]=0;
            q.emplace(i);
        }
        while(!q.empty()){
            int u=q.front();
            q.pop();
            for(int v:adj[u])if(match[v]!=-1&&lv[match[v]]==-1){
                lv[match[v]]=lv[u]+1;
                q.emplace(match[v]);
            }
        }
    }
    bool dfs(int u){
        for(int &i=ptr[u];i<adj[u].size();i++){
            int v=adj[u][i];
            if(match[v]==-1||(lv[match[v]]==lv[u]+1&&dfs(match[v]))){
                match[u]=v,match[v]=u;
                return true;
            }
        }
        return false;
    }
    int max_matching(){
        int ans=0,cnt=0;
        match.assign(n+m,-1);
        do{
            ptr.assign(n,0);
            bfs();
            cnt=0;
            for(int i=0;i<n;i++)if(match[i]==-1&&dfs(i))cnt++;
            ans+=cnt;
        }while(cnt);
        return ans;
    }
};
#line 4 "verify/flows/hopcroft-karp/bipartitematching.test.cpp"

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    int n,m,e;
    cin >> n >> m >> e;
    HopcroftKarp bm(n,m);
    for(int i=0;i<e;i++){
        int u,v;
        cin >> u >> v;
        bm.add_edge(u,v);
    }
    cout << bm.max_matching() << "\n";
    for(int i=0;i<n;i++){
        if(bm.match[i]!=-1){
            cout << i << " " << bm.match[i]-n << "\n";
        }
    }
}

Back to top page