# Cod sursa(job #1494196)

Utilizator Data 30 septembrie 2015 20:07:37 Cuplaj maxim in graf bipartit 100 cpp done Arhiva educationala 1.09 kb
``````#include <stdio.h>
#include <vector>

#define maxdim 100005

using namespace std;

int n, m, edges;
int viz[maxdim], l[maxdim], r[maxdim];
vector<int> G[maxdim];

bool cuplaj(int nod) {
if (viz[nod]) {
return false;
}
viz[nod] = true;

for (int other : G[nod]) {
if (!r[other]) {
l[nod] = other;
r[other] = nod;
return true;
}
}

for (int other : G[nod]) {
if (cuplaj(r[other])) {
l[nod] = other;
r[other] = nod;
return true;
}
}

return false;
}

int main() {

freopen("cuplaj.in", "r", stdin);
freopen("cuplaj.out", "w", stdout);

scanf("%d %d %d", &n, &m, &edges);
for (int i = 1; i <= edges; ++i) {
int x, y; scanf("%d %d", &x, &y);
G[x].push_back(y);
}

int updated = 1;
while (updated) {
updated = 0;
for (int i = 1; i <= n; ++i) {
viz[i] = 0;
}
for (int i = 1; i <= n; ++i) {
if (!l[i]) {
updated |= cuplaj(i);
}
}
}

int cardinal = 0;
for (int i = 1; i <= n; ++i) {
cardinal += l[i] != 0;
}
printf("%d\n", cardinal);
for (int i = 1; i <= n; ++i) {
if (l[i] != 0) {
printf("%d %d\n", i, l[i]);
}
}

return 0;
}
``````