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;
}