Thuật toán Hopcroft-Karp tìm cặp ghép cực đại trên đồ thị 2 phía

#include <bits/stdc++.h>
using namespace std;
#define nmax 1001
#define mmax 1000001
int p, q, m;
int head[nmax], link[mmax], adj[mmax], match[nmax];
bool found, avail[nmax];
void enter() {
    cin >> p >> q >> m;
    memset(head, 0, sizeof head);
    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;
        adj[i] = v;
        link[i] = head[u];
        head[u] = i;
    }
}
void DFSVisit(int x) {
    for (int i = head[x]; i; i = link[i]) {
        int y = adj[i];
        if (avail[y]) {
            avail[y] = 0;
            if (!match[y])
                found = true;
            else
                DFSVisit(match[y]);
            if (found) {
                match[y] = x;
                return;
            }
        }
    }
}
void bmatch() {
    memset(match, 0, sizeof match);
    vector<int> X;
    for (int x = 1; x <= p; x++) X.push_back(x);
    while (1) {
        int cnt = X.size();
        memset(avail + 1, 1, q * sizeof(avail[1]));
        for (int i = 0; i < X.size();) {
            found = 0;
            DFSVisit(X[i]);
            if (found) {
                X[i] = X.back();
                X.pop_back();
            } else
                i++;
        }
        if (!X.size() || X.size() == cnt)
            break;
    }
    int cnt = 0;
    for (int y = 1; y <= q; y++) cnt += (match[y] != 0);

    cout << cnt << '\n';
    for (int y = 1; y <= q; y++)
        if (match[y])
            cout << match[y] << ' ' << y << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    enter();
    bmatch();
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct matcher {
    const int oo = 100000000;
    int m, n;
    vector<int> mx, my, dist;
    vector<vector<int>> ke;
    int matched;

    matcher(int m, int n):
        m(m), n(n),
        mx(m+1, 0), my(n+1, 0), dist(m+1),
        ke(m+1),
        matched(0) {}

    void add_edge(int u, int v) {
        ke[u].push_back(v);
    }

    bool bfs() {
        queue<int> Q;
        for (int u=1; u<=m; u++) {
            if (!mx[u]) {
                dist[u] = 0;
                Q.push(u);
            } else {
                dist[u] = oo;
            }
        }

        bool found = false;
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            for (int v: ke[u]) {
                if (!my[v]) {
                    found = true;
                } else if (dist[my[v]] == oo) {
                    dist[my[v]] = dist[u] + 1;
                    Q.push(my[v]);
                }
            }
        }

        return found;
    }

    bool dfs(int u) {
        if (dist[u] == oo) return false;
        for (int v: ke[u]) {
            if (!my[v] || (dist[my[v]]==dist[u]+1 && dfs(my[v]))) {
                mx[u] = v;
                my[v] = u;
                return true;
            }
        }
        return false;
    }

    void match() {
        while(bfs()) {
            for (int u=1; u<=m; u++) if (!mx[u]) matched += dfs(u);
        }
    }
};

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int m, n, u, v, es; cin >> m >> n >> es;
    matcher z(m, n);
    while (es--) {
        cin >> u >> v;
        z.add_edge(u, v);
    }
    z.match();
    cout << z.matched << '\n';
    for (int u=1; u<=z.m; u++) if (z.mx[u]) cout << u << ' ' << z.mx[u] << '\n';
    return 0;
}

//nhatnguyendrgs (c) 2015 - hopcroft_karp.cpp

#include "iostream"
#include "stdio.h"
#include "stdlib.h"
#include "string"
#include "string.h"
#include "algorithm"
#include "math.h"
#include "vector"
#include "map"
#include "queue"
#include "stack"
#include "deque"
#include "set"
using namespace std;

typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
const int inf = 1e9;
const int MaxN = 1e5;

vector<vi> Adj;
int n, m, match[MaxN+4], dist[MaxN+4],u,v;

bool bfs() {
    queue<int> Q;
    for (int i = 1; i <= n; ++i) {
        if (match[i] == 0) {
            dist[i] = 0;
            Q.push(i);
        }
        else dist[i] = inf;
    }
    dist[0] = inf;
    while (!Q.empty()) {
        int u = Q.front(); Q.pop();
        if (u != 0) {
            for (int j = 0; j<Adj[u].size(); ++j) {
                int v=Adj[u][j];
                if (dist[match[v]] == inf) {
                    dist[match[v]] = dist[u] + 1;
                    Q.push(match[v]);
                }
            }
        }
    }
    return (dist[0] != inf);
}

bool dfs(int u) {
    if (u != 0) {
        for (int j = 0; j<Adj[u].size(); ++j) {
            int v = Adj[u][j];
            if (dist[match[v]] == dist[u] + 1) {
                if (dfs(match[v])) {
                    match[v] = u;
                    match[u] = v;
                    return true;
                }
            }
        }
        dist[u] = inf;
        return false;
    }
    return true;
}

void hopcroft_karp() {
    vii result;int matching = 0;
    while (bfs())
    for (int i = 1; i <= n; i++)
        if (match[i] == 0 && dfs(i))
            matching++;
    printf("%d\n", matching);
    for (int  i=1;i<=n;i++)
    if (match[i] != 0) printf("%d %d\n",i,match[i]-n);
}

int main() {
    scanf("%d%d", &n, &m);
    Adj.assign(MaxN+4,vi());
    while (scanf("%d%d",&u,&v)!=EOF){
        v += n;
        Adj[u].push_back(v);
        Adj[v].push_back(u);
    }
    hopcroft_karp();
    return 0;
}