Cod sursa(job #431562)

Utilizator Andrei_ScorpioAndreiana Andrei Daniel Andrei_Scorpio Data 1 aprilie 2010 10:02:09
Problema Cuplaj maxim in graf bipartit Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.82 kb
#include<stdio.h>
#define Nmax 100010
#define Mmax 200010
struct nod
{
	int inf;
	nod *urm;
}*a[Nmax],*s[Nmax];
int niv[Nmax],nivmin[Nmax],cr[Nmax],ncr,t[Nmax],pam[Nmax];
int n,m,viz[Nmax];
int sol[Mmax][2],nr;
void listare(int a1,int b1,int &poz)
{
 nod *p;
 
 	 if(pam[sol[poz][0]]!=ncr)
	 {	p=new nod;
		 p->inf=sol[poz][0];
		 p->urm=s[ncr];
		 s[ncr]=p;
		 pam[sol[poz][0]]=ncr;
	 }
	 if(pam[sol[poz][1]]!=ncr)
	 {	p=new nod;
		 p->inf=sol[poz][1];
		 p->urm=s[ncr];
		 s[ncr]=p;
		 pam[sol[poz][1]]=ncr;
	 }
 if(!((sol[poz][0]==a1 && sol[poz][1]==b1) || (sol[poz][1]==a1 && sol[poz][0]==b1)))
 {
	poz--;
	 listare(a1,b1,poz);
 }
}

void DF(int x)
{
	nod *p;
	for(p=a[x];p!=NULL;p=p->urm)
	{
		if( t[x]!=p->inf)
		{
		if(viz[p->inf]!=0)
		{
			
			if(niv[p->inf]<nivmin[x])
				nivmin[x]=niv[p->inf];
		}
		else
		{
			t[p->inf]=x;
			viz[p->inf]=viz[x];
			niv[p->inf]=niv[x]+1;
			nivmin[p->inf]=niv[p->inf];
			nr++;
			sol[nr][0]=x;
			sol[nr][1]=p->inf;
			DF(p->inf);
			
			if(nivmin[p->inf]<nivmin[x])
				nivmin[x]=nivmin[p->inf];
			
			if(nivmin[p->inf]>=niv[x])
			{
				
				ncr++;
				listare(x,p->inf,nr);
				nr--;
				
				
			}
		}
		}
	}
}
int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	scanf("%d %d",&n,&m);
	int i,x,y;
	nod *p;
	nr--;
	for(i=0;i<m;i++)
	{
		scanf("%d %d",&x,&y);
		p=new nod;
		p->inf=y;
		p->urm=a[x];
		a[x]=p;
		p=new nod;
		p->inf=x;
		p->urm=a[y];
		a[y]=p;
	}
	
	niv[1]=1;
	viz[1]=1;
	nivmin[1]=1;
	t[1]=1;
	DF(1);
	/*int ok=0;
	if(nr>=0)
	{listare(sol[0][0],sol[0][1],nr);
	ok=1;}
	if(ok)
		
	else
		printf("%d\n",ncr-1);*/
	printf("%d\n",ncr);
	for(i=1;i<=ncr;i++)
	{
		for(p=s[i];p!=NULL;p=p->urm)
			printf("%d ",p->inf);
		printf("\n");
	}
	return 0;
}