Cod sursa(job #574018)

Utilizator horeste12Stoianovici Horatiu Andrei horeste12 Data 6 aprilie 2011 19:17:25
Problema Componente biconexe Scor 28
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 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)
{
	nrsol++;
	int i;
	for(i=1;i<=x&&!q[i];i++)
		;
	NOD *p;
	p=sol[nrsol];
	for(;i<=x;i++)
	{
		p=new NOD;
		if(viz[q[i]]==1)
		{
			viz[q[i]]++;
			p->inf=q[i];p->urm=sol[nrsol];sol[nrsol]=p;
		}
		q[i]=0;
	}
}

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;
				int iaux=ind;
				t[p->inf]=k;
				DF(p->inf,nivel+1);
				if(nivm[p->inf]>=niv[k])
					compon(iaux-2);
				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)
		{
			fprintf(g,"%d ",p->inf);
			p=p->urm;
		}
		fprintf(g,"\n");
	}
}

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