Cod sursa(job #574062)

Utilizator horeste12Stoianovici Horatiu Andrei horeste12 Data 6 aprilie 2011 19:43:56
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.64 kb
#include<cstdio>

using namespace std;

typedef struct nod
{
	int inf;
	nod *urm;
} NOD;

typedef NOD *graf[100010];

graf G;
graf sol;

FILE *f;
FILE *g;

int n,m,niv[100010],nivm[100010],viz[100010],t[100010],q[200010],ind=1,nrsol;

void citire()
{
	f=fopen("biconex.in","r");
	fscanf(f,"%d %d",&n, &m);
	int x,y;
	NOD *p;
	for(int i=1;i<=m;i++)
	{
		fscanf(f,"%d %d",&x,&y);
		p=new NOD; p->inf=y; p->urm=G[x]; G[x]=p;
		p=new NOD; p->inf=x; p->urm=G[y]; G[y]=p;
	}
}
void regulate()
{
	for(int i=1;i<=n;i++)
		if(viz[i])
			viz[i]=1;
}

void compon(int x, int y)
{
	nrsol++;
	int a,b;
	NOD *p;
	do
	{
		a=q[ind-1];b=q[ind-2];
		p=new NOD;
		p->inf=a;p->urm=sol[nrsol];sol[nrsol]=p;
		p=new NOD;
		p->inf=b;p->urm=sol[nrsol];sol[nrsol]=p;
		ind-=2;
	} while(a!=y||b!=x);
}

void DF(int k, int nivel)
{
	niv[k]=nivm[k]=nivel;
	NOD *p;
	p=G[k];viz[k]=1;
	while(p)
	{
		if(p->inf!=t[k])
		{
			if(!viz[p->inf])
			{
				q[ind++]=k;q[ind++]=p->inf;
				t[p->inf]=k;
				DF(p->inf,nivel+1);
				if(nivm[p->inf]>=niv[k])
					compon(k,p->inf);
				if(nivm[k]>nivm[p->inf])
					nivm[k]=nivm[p->inf];
			}
			else
				if(nivm[k]>nivm[p->inf])
					nivm[k]=nivm[p->inf];
		}
		p=p->urm;
	}
}

void afis()
{
	g=fopen("biconex.out","w");
	fprintf(g,"%d\n",nrsol);
	for(int i=1;i<=nrsol;i++)
	{
		NOD *p;
		p=sol[i];
		while(p)
		{
			viz[p->inf]=0;
			p=p->urm;
		}
		p=sol[i];
		while(p)
		{
			if(!viz[p->inf])
			{
				fprintf(g,"%d ",p->inf);
				viz[p->inf]=1;
			}
			p=p->urm;
		}
		fprintf(g,"\n");
	}
}

int main()
{
	citire();
	DF(1,1);
	afis();
	return 0;
}