# Cod sursa(job #1809918)

Utilizator Data 19 noiembrie 2016 13:37:47 Cuplaj maxim in graf bipartit 100 cpp done Arhiva educationala 1.15 kb
#include <stdio.h>
#include <vector>
#include <string.h>
#define NMAX 10010
using namespace std;

vector<int> G[NMAX];
bool done, viz[NMAX];
int L[NMAX], R[NMAX], N, M, E, i, a, b, cuplaj;

bool pairup(int n) {
if (viz[n]) {
return false;
}
viz[n] = true;

for (vector<int>::iterator it = G[n].begin(); it != G[n].end(); it++) {
if (!R[*it] || pairup(R[*it])) {
L[n] = *it;
R[*it] = n;
return true;
}
}

return false;
}

int main(int argc, char **argv)
{
freopen("cuplaj.in", "r", stdin);
freopen("cuplaj.out", "w", stdout);

scanf("%d %d %d", &N, &M, &E);
for (i = 1; i <= E; i++) {
scanf("%d %d", &a, &b);
G[a].push_back(b);
}

while (!done) {
done = true;
memset(viz, false, sizeof(viz));

for (i = 1; i <= N; i++) {
if (!L[i] && pairup(i)) {
cuplaj++;
done = false;
}
}
}

printf("%d\n", cuplaj);
for (i = 1; i <= N; i++) {
if (L[i]) {
printf("%d %d\n", i, L[i]);
}
}

return 0;
}