MATCH1 - Cặp ghép không trọng số
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<bits/stdc++.h>
using namespace std;
#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int N = 100;
int nx, ny;
vector<int> g[N];
void enter() {
cin >> nx >> ny;
for(int u, v; cin >> u >> v; )
g[u-1].push_back(v-1);
}
void maxmatch() {
vector<int> matchX (nx, -1);
vector<int> matchY (ny, -1);
int mxmatch = 0;
while(true) {
vector<int> trace (ny, -1); queue<int> q;
for(int i = 0; i < nx; ++i)
if(matchX[i] == -1) q.push(i);
int f = -1;
for(bool stop = false; !stop && !q.empty(); ) {
int u = q.front(); q.pop();
TR(g[u], v) if(trace[*v] == -1) {
trace[*v] = u;
if(matchY[*v] == -1) {
stop = true; f = *v;
break;
} else q.push(matchY[*v]);
}
}
if(f == -1) break;
do {
int x = trace[f], next = matchX[x];
matchX[x] = f; matchY[f] = x;
f = next;
} while(f != -1);
++mxmatch;
}
cout << mxmatch << '\n';
for(int i = 0; i < nx; ++i) if(matchX[i] != -1)
cout << i+1 << ' ' << matchX[i]+1 << '\n';
}
int main() {
ios::sync_with_stdio(false);
enter();
maxmatch();
return 0;
}