Cod sursa(job #270746)

Utilizator c_e_manuEmanuel Cinca c_e_manu Data 4 martie 2009 15:05:45
Problema Componente biconexe Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 1.52 kb
#include<fstream.h>
#define N 100001
#define M 200001

ifstream fin("biconex.in");
ofstream fout("biconex.out");

struct nod{
	int info;
	nod *urm;
	};
nod *prim[N],*comp[N];

struct muchie {
	int x,y;
	};
muchie v[M];

int n,m,niv[N],p,viz[N],kappa,sel[N];

void insert(int where, int what)
{       nod *p=new nod;
	p->info=what;
	p->urm=prim[where];
	prim[where]=p;
}

void insert2(int where, int what)
{	nod *p=new nod;
	p->info=what;
	p->urm=comp[where];
	comp[where]=p;
}

void read()
{	int x,y,i;
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{       fin>>x>>y;
		insert(x,y);
		insert(y,x);
	}
}

void compBicon(int k, int i)
{       int j;
	memset(sel,0,N);
	do
	{       sel[v[p].x]=sel[v[p].y]=1;
		p--;
	}
	while(!(v[p+1].x==k&&v[p+1].y==i));
	for(j=1;j<=n;j++)
		if(sel[j])
			insert2(kappa,j);
}

void dfs(int k, int tk, int &nivmin)
{	int nivmin1,X;
	nod *q;
	viz[k]=1;niv[k]=niv[tk]+1;
	for(q=prim[k];q;q=q->urm)
		if(!viz[q->info])
		{	X=q->info;
			p++;
			v[p].x=k;
			v[p].y=X;
			nivmin1=niv[k]+1;
			dfs(X,k,nivmin1);
			if(nivmin1<nivmin) nivmin=nivmin1;
			if(nivmin1>=niv[k])
			{       kappa++;
				compBicon(k,X);
			}
		}
		else
		{	if(viz[q->info]&&q->info!=tk)
				if(niv[q->info]<nivmin)
					nivmin=niv[q->info];
		}
}
void write()
{	fout<<kappa<<'\n';
	for(int i=1;i<=kappa;i++)
	{	for(nod *q=comp[i];q;q=q->urm)
			fout<<q->info<<' ';
		fout<<'\n';
	}
}

int main()
{       int aux=1;
	read();
	niv[0]=0;
	dfs(1,0,aux);
	write();
	return 0;
}