NKBM - Cặp ghép cực đại trên đồ thị hai phía

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>
const int N = 1010;
using namespace std;
int matchX[N], matchY[N], Q[N], T[N];
int m, n, e;
vector<int> a[N];

int BFS() {
    int l = 1, r = 0, i, u, v;
    for(i = 1; i <= m; i++)
        if (matchX[i] == 0) Q[++r] = i;
    for(i = 1; i <= n; i++) T[i] = 0;
    while (l <= r) {
        u = Q[l++];
        for(i = 0; i < a[u].size(); i++) {
            v = a[u][i];
            if (T[v] == 0) {
                T[v] = u;
                if (matchY[v] == 0) return v;
                else Q[++r] = matchY[v];
            }
        }
    }
    return 0;
}

void Enlarge(int y) {
    int next, x;
    for(; y; y = next) {
        x = T[y];
        next = matchX[x];
        matchX[x] = y;
        matchY[y] = x;
    }
}

int main() {
    scanf("%d %d %d", &m, &n, &e);
    int i, u, v;
    for(i = 1; i <= e; i++) {
        scanf("%d %d", &u, &v);
        a[u].push_back(v);
    }
    while (i = BFS()) Enlarge(i);
    int res = 0;
    for(i = 1; i <= m; i++) if (matchX[i] != 0) res++;
    printf("%d\n", res);
}

Download