Cod sursa(job #497039)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 1 noiembrie 2010 15:07:17
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.71 kb
#include <stdio.h>

const int maxn=100001,maxm=200001;
struct nod {
	int inf;
	nod *next;
} *A[maxn],*Sol[maxn];
struct arc{
	int a,b;
} st[maxm];
int i,N,M,NR,index,k,ind[maxn],low[maxn],t[maxn];
void add(int x, int y)
{
	nod *q=new nod;
	q->inf=y;
	q->next=A[x];
	A[x]=q;
}

void citire()
{
	int x,y;
	scanf("%d %d",&N,&M);
	for(i=1;i<=M;i++)
	{
		scanf("%d %d",&x,&y);
		add(x,y);
		add(y,x);
	}
}

int min(int a, int b)
{
	if(a<b) return a;
	return b;
}

void add_stiva(int x, int y)
{
	k++;
	st[k].a=x;
	st[k].b=y;	
}

void adauga_sol(int p)
{
	NR++;
	while(st[k].a!=p)
	{
		nod *s=new nod;
		s->inf=st[k].b;
		s->next=Sol[NR];
		Sol[NR]=s;
		k--;
	}
	nod *s=new nod;
	s->inf=st[k].b;
	s->next=Sol[NR];
	Sol[NR]=s;
	s=new nod;
	s->inf=st[k].a;
	s->next=Sol[NR];
	Sol[NR]=s;
	k--;
}

void dfs(int p)
{
	ind[p]=++index;
	low[p]=index;
	for(nod *x=A[p];x;x=x->next) //verificam vecinii
	{
		if(x->inf!=t[p]) //daca nu e tatal
		{
			if(ind[x->inf]==0) //daca nu a fost vizitat inca
			{
				t[x->inf]=p;
				add_stiva(p,x->inf); //adaug muchia in stiva
				dfs(x->inf); //il vizitez
				low[p]=min(low[p],low[x->inf]);
				if(ind[p]<=low[x->inf]) //daca din fii se poate ajunge doar pana la tata sau mai jos
					adauga_sol(p);
			}
			else //update pana unde poate ajunge pe muchia de intoarcere
				low[p]=min(low[p],ind[x->inf]);
		}
	}
}

void afisare()
{
	printf("%d\n",NR);
	for(i=1;i<=NR;i++)
	{
		for(nod *x=Sol[i];x;x=x->next)
		{
			printf("%d ",x->inf);
		}
		printf("\n");
	}
	
}

int main()
{
	freopen("biconex.in","r",stdin);
	freopen("biconex.out","w",stdout);
	citire();
	for(i=1;i<=N;i++) t[i]=-1;
	dfs(1);
	afisare();
}