Cod sursa(job #279147)

Utilizator raula_sanChis Raoul raula_san Data 12 martie 2009 18:11:26
Problema Cuplaj maxim in graf bipartit Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>

#define MAX_N 10001

struct nod
{
	int v;
	nod *next;

} *L[MAX_N];

int St[MAX_N], Dr[MAX_N], U[MAX_N];
int N, M, E;

int Cuplaj(int nd)
{
	if(U[nd]) return 0;
	U[nd] = 1;

	nod *p;

	for ( p = L[nd]; p; p = p->next )
		if(!St[p->v] || Cuplaj(St[p->v]))
		{
			Dr[nd] = p->v;
			St[p->v] = nd;
			return 1;
		}

	return 0;
}

int main()
{
	freopen("cuplaj.in", "rt", stdin);
	freopen("cuplaj.out", "wt", stdout);

	int i, x, y;
	for ( scanf("%d %d %d", &N, &M, &E), i = 1; i <= E; ++i )
	{
		scanf("%d %d", &x, &y);

		nod *p = new nod;
		p->v = y;
		p->next = L[x];
		L[x] = p;
	}

	int e = 1;

	while(e)
	{

		e = 0;
		for ( i = 1; i <= N; ++i )
			U[i] = 0;

		for ( i = 1; i <= N; ++i )
			if(!Dr[i]) e |= Cuplaj(i);
	}

	int r = 0;
	for ( i = 1; i <= N; ++i )
		r += Dr[i] > 0;

	printf("%d\n", r);
	for ( i = 1; i <= N; ++i )
		if(Dr[i])
			printf("%d %d\n", i, Dr[i]);


	fclose(stdin);
	fclose(stdout);
	return 0;
}