Cod sursa(job #1155365)

Utilizator myshuSpatariu Mihai-Constantin myshu Data 26 martie 2014 20:56:31
Problema Componente biconexe Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.67 kb
#include<fstream>
using namespace std;
struct nod{int info ;
			nod * urm;}v[100001],*p,*w[100001];
int x,y,u,cc[200001],poz[100001],poz2[100001],c[100001],ccc[100001],u2,pozc[100001];
void df(int x,int y)
{
	nod *q;
	q=&v[x];
	ccc[++u2]=x;
	pozc[x]=u2;
		while(q->urm!=NULL)
		{
			if(poz[q->urm->info]!=0){if(q->urm->info!=y&&c[q->urm->info]==0)c[x]=q->urm->info;}
			else {poz[q->urm->info]=x;
				  df(q->urm->info,x);}
			if(q!=NULL)q=q->urm;
			if(q==NULL)break;
		}
}
void conex()
{int x2,y2;
	if(y!=c[ccc[x]])
	{
		cc[++u]=y;
		poz2[y]=1;
		y=poz[y];
	}
	while(y!=c[ccc[x]])
			 {
			  cc[++u]=y;
			  if(c[y]!=0)
			  {
				x2=x;y2=y;
				x=pozc[y];y=c[x];
				conex();
				x=x2;y=y2;
			  }
			  poz2[y]=1;
			  y=poz[y];
			  }
	if(poz2[y]==0)
		{
		 cc[++u]=y;
		 cc[++u]=-1;
		}
}
int main()
{
	int n,m,i,k=0;
	ifstream fcin("biconex.in");
	ofstream fcout("biconex.out");
	fcin>>n>>m;
	for(i=1;i<100001;i++)
		{v[i].info=0;v[i].urm=NULL;w[i]=&v[i];}
	for(i=1;i<=m;i++)
	{	fcin>>x>>y;
		v[x].info++;
		p=new nod;
		p->info=y;
		p->urm=NULL;
		w[x]->urm=p;
		w[x]=p;
		v[y].info++;
		p=new nod;
		p->info=x;
		p->urm=NULL;
		w[y]->urm=p;
		w[y]=p;
	}	
	poz[1]=-1;
	df(1,-1);
	x=u2;
	while(x!=1)
	{
		if(poz2[ccc[x]]==0)
		{
		if(c[ccc[x]]!=0)
			{y=ccc[x];k++;
			 conex();
			 /*while(y!=c[ccc[x]])
			 {cc[++u]=y;
			  poz2[y]=1;
			  y=poz[y];}
			 cc[++u]=y;
			 cc[++u]=-1;*/
			}
		else {k++;cc[++u]=ccc[x];poz2[ccc[x]]=1;cc[++u]=poz[ccc[x]];cc[++u]=-1;}
		}
		x--;
	}
	fcout<<k<<'\n';
	u=1;
	while(k!=0)
	{
		while(cc[u]!=-1)
			{fcout<<cc[u]<<' ';u++;}
		fcout<<'\n';u++;
		k--;
	}
	return 0;
}