MATCH1 - Cặp ghép không trọng số

Tác giả: ladpro98

Ngôn ngữ: C++

#include <bits/stdc++.h>

using namespace std;

struct BipartiteGraph {
    vector<vector<int> > E;
    vector<vector<pair<int, int> > > a;
    vector<int> match;
    vector<int> edgeMatch;
    vector<bool> was;
    int m, n;

    BipartiteGraph(int m, int n) {
        this->m = m; this->n = n;
        E.clear();
        a.clear();
        a.resize(m);
        match.assign(n, -1);
        edgeMatch.assign(n, -1);
        was.assign(n, false);
    }

    void addEdge(int u, int v, vector<int> expression) {
        int index = E.size();
        a[u].push_back(make_pair(v, index));
        E.push_back(expression);
    }

    bool dfs(int u) {
        for (int i = 0; i < a[u].size(); ++i) {
            int v = a[u][i].first;
            if (was[v]) continue;
            was[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                edgeMatch[v] = a[u][i].second;
                return true;
            }
        }
        return false;
    }

    int fastMatch() {
        vector<int> buffer;
        for (int i = 0; i < m; ++i) buffer.push_back(i);
        bool stop = false;
        int ans = 0;
        do {
            stop = true;
            for (int i = 0; i < n; ++i) was[i] = false;
            for (int i = (int)buffer.size() - 1; i >= 0; --i) {
                int u = buffer[i];
                if (dfs(u)) {
                    ++ans;
                    stop = false;
                    buffer[i] = buffer.back();
                    buffer.pop_back();
                }
            }
        } while (!stop);
        return ans;
    }
};

int main() {
    ios::sync_with_stdio(false);
    int n, m; cin >> m >> n;
    BipartiteGraph G(m, n);
    int u, v;
    while (cin >> u >> v)
        G.addEdge(--u, --v, vector<int>());
    cout << G.fastMatch() << endl;
    for (int i = 0; i < n; ++i) if (G.match[i] != -1)
        cout << G.match[i] + 1 << ' ' << i + 1 << '\n';
    return 0;
}

Download