# Cod sursa(job #1545611)

Utilizator Data 6 decembrie 2015 21:37:21 Cuplaj maxim in graf bipartit 24 cpp done Arhiva educationala 1.87 kb
``````/*
Cat timp S-A EFECTUAT CUPLARE
pentru fiecare v din V1
daca (!M1[v] ) atuci cupleaza(v);

unde M1(v) = suprafata cuplata cu V
M2(x) = lungimea?? cuplata cu Suprafata x ?????

bool cupleaza(v)
daca  a fost folosit v atuci return false;
pentru fiecare x adiacent v executa
daca (!M2[x]) atunci
M1[v] = x si M2[x] = v;
return true
pentru fiecare x adiacent v executa
daca ( cupleaza( M2[x] )  )
M1[v] = x; M2[x] = v;
return true;

*/

#include <iostream>
#include <fstream>
#include <string.h>
#include <vector>
//#include <queue>
//#include <algorithm>

using namespace std;
const int nmax = 10001;

vector <int> a[nmax], b[nmax];
int ap[nmax], bp[nmax];									// pairs of the nodes
char folosit[nmax];
int la,lb;

bool cuplare(int v);

int main(){
freopen("cuplaj.in", "r", stdin);
freopen("cuplaj.out", "w", stdout);
int m,x,y;
scanf("%d %d %d", &la, &lb, &m);
for (int i = 0; i < m; i++) {
scanf("%d %d", &x, &y);
a[x].push_back(y);
}

// initial
int nrCuplaje = 0;
memset(ap, 0, 4 * (la + 2));
memset(bp, 0, 4 * (lb + 2));
// apgorimul
bool changed = true;
while (changed) {
changed = false;
memset(folosit, 0, la + 1);
for (int i = 1; i <= la; i++) {
if (!ap[i]) {
if (cuplare(i)) {
changed = true;
nrCuplaje++;
}
}
}
}

printf("%d \n", nrCuplaje);
for (int i = 1; i <= la; i++)
if (ap[i] != 0 )	printf("%d %d\n", i, ap[i]);
fclose(stdin);
fclose(stdout);
return 0;
}

bool cuplare(int v) {
if (folosit[v] != 0) return false;

folosit[v] = 1;
for (int ii = 0; ii < a[v].size(); ii++)
if (bp[a[v][ii]] == 0) {
ap[v] = a[v][ii];
bp[a[v][ii]] = v;
return true;
}
for (int ii = 0; ii < a[v].size(); ii++)
if (cuplare(ap[a[v][ii]])) {
ap[v] = a[v][ii];
bp[a[v][ii]] = v;
return true;
}
return false;

}``````