Cod sursa(job #555545)

Utilizator selea_teodoraSelea Teodora selea_teodora Data 15 martie 2011 16:33:22
Problema Componente biconexe Scor 44
Compilator cpp Status done
Runda Arhiva educationala Marime 2.47 kb
#include<fstream>
using namespace std;
int n,m,dfn[100005],low[100005];
long con[1005][1005],contor;
typedef
struct nod
{
	int nr;
	nod *urm;
}*Pnod;
typedef
struct stiva
{
	int a,b;
	stiva*urm;
}*Pstiva;
Pnod l[100005],sol[100005];
Pstiva st[100005],vf;
ofstream fout("biconex.out");
void quick(int inf, int sup)
{
	if(inf<sup)
	{
		int pivot=con[contor][inf],aux;
		int i=inf+1,j=sup;
		while(i<=j)
		{
			while(i<=sup&&con[contor][i]<=pivot)
				i++;
			while(j>=inf&&con[contor][j]>pivot)
				j--;
			if(i<j&&i<=sup&&j>=inf)
			{aux=con[contor][i];
			con[contor][i]=con[contor][j];
			con[contor][j]=aux;
			i++;
			j--;
			}
		}
		i--;
		con[contor][inf]=con[contor][i];
		con[contor][i]=pivot;
		quick(inf,i-1);
		quick(i+1,sup);
	}
}
void componenta(int x, int y)
{
	int tx=0,ty=0,sw=0,i;
	contor++;
	Pnod q;
	while(sw!=2)
	{
		
		con[contor][0]++;
		/*q=new(nod);
		q->nr=vf->a;
		q->urm=sol[contor];
		sol[contor]=q;*/
		con[contor][con[contor][0]]=vf->a;
		if(vf->a==x&&tx==0)
			tx++;
		else if(vf->a==y&&ty==0)
			ty++;
		con[contor][0]++;
		/*q=new(nod);
		q->nr=vf->b;
		q->urm=sol[contor];
		sol[contor]=q;*/
		con[contor][con[contor][0]]=vf->b;
		if(vf->b==x&&tx==0)
			tx++;
		else if(vf->b==y&&ty==0)
			ty++;;
		vf=vf->urm;
		sw=tx+ty;
	}
	quick(1,con[contor][0]);
	int val;
	i=1;
	while(i<=con[contor][0])
		{
			val=con[contor][i];
			q=new(nod);
			q->nr=con[contor][i];
			q->urm=sol[contor];
			sol[contor]=q;
			i++;
			while(con[contor][i]==val)
				i++;
			//fout<<con[contor][i]<<"  ";
	}
	
}

void df(int n,int fn,int nivel)
{
	Pnod p;
	Pstiva r;
	dfn[n]=low[n]=nivel;
	for(p=l[n];p!=NULL;p=p->urm)
		if(p->nr!=fn)
		if(dfn[p->nr]==-1)
			{
				r=new(stiva);
				r->a=n;
				r->b=p->nr;
				r->urm=vf;
				vf=r;
				df(p->nr,n,nivel+1);
				if(low[n]>low[p->nr])
					low[n]=low[p->nr];
				if(low[p->nr]>=dfn[n])
					componenta(n,p->nr);
					//fout<<n<<" ";
		}
		else
			if(low[n]>low[p->nr])
				low[n]=low[p->nr];
}

		
			
int main()
{
	ifstream fin("biconex.in");
	fin>>n>>m;
	int i,j;
	Pnod p;
	while(fin>>i>>j)
	{
		p=new(nod);
		p->nr=j;
		p->urm=l[i];
		l[i]=p;
		p=new(nod);
		p->nr=i;
		p->urm=l[j];
		l[j]=p;
	}
	fin.close();
	for(i=1;i<=n;i++)
		dfn[i]=-1;
	df(1,0,0);
	fout<<contor<<'\n';
	for(i=1;i<=contor;i++)
	{
		p=sol[i];
		while(p)
		{
			fout<<p->nr<<" ";
			p=p->urm;
		}
		fout<<'\n';
	}
	fout.close();
	return 0;
}