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

Download