Cod sursa(job #729883)

Utilizator ILDottoreBogdan Stoian ILDottore Data 30 martie 2012 17:48:08
Problema Cuplaj maxim in graf bipartit Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;

#define NMAX 10005

FILE *f=fopen("cuplaj.in","r");
FILE *g=fopen("cuplaj.out","w");

vector<int> ST[NMAX];

long n,m,e,cst[NMAX],cdr[NMAX],U[NMAX],nr;

int cupleaza(long nod)
{
	
	if (U[nod]) return 0;
	U[nod]=1;
	
	for (long i=0;i<ST[nod].size();i++)
	{   
		long nod_dr=ST[nod][i];
		if (!cdr[nod_dr] || cupleaza( cdr[nod_dr] ) )
		{  cdr[nod_dr]=nod;
		   cst[nod]=nod_dr;
		   return 1;
		}
	}
	return 0;
}


int main()
{
	fscanf(f,"%ld%ld%ld",&n,&m,&e);
	
	for (long i=1;i<=e;i++)
	{long x,y;
	fscanf(f,"%ld%ld",&x,&y);
	ST[x].push_back(y);
	}
	
	int change=1;
	
	while (change)
	{memset(U,0,sizeof(U));
	 change=0;
	 
	for (long i=1;i<=n;i++)
		{
		if (cst[i]) continue;
		if ( cupleaza(i) ) {nr++;change=1;}
		}
	}
	
	fprintf(g,"%ld\n",nr);
	
	for (long i=1;i<=n;i++)
		if(cst[i])
			fprintf(g,"%ld %ld\n",i,cst[i]);
		
return 0;}