Cod sursa(job #235861)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 26 decembrie 2008 02:19:41
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include<stdio.h>
#define N 100001
struct nod{int inf;nod *urm;};
nod *v[N],*C[N];
int n,m,i,a,b,viz[N],stiva[N],low[N],dsfnum[N],top,num,nc;
void readd(),solve(),visit(int p),prints();
int main()
{
	readd();
	solve();
	prints();
	return 0;
}
void readd()
{       nod *paux;
	freopen("ctc.in","rt",stdin);
	freopen("ctc.out","wt",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{ scanf("%d%d",&a,&b);
	  paux=new nod;
	  paux->inf=b;
	  paux->urm=v[a];
	  v[a]=paux;
	}
}
void solve()
{   for(i=1;i<=n;i++)
	if(!viz[i])visit(i);
}

void visit(int p)
{   nod *paux;
    viz[p]=1;
    stiva[++top]=p;//add p to L
    dsfnum[p]=num++;//increment N
    low[p]=dsfnum[p];
    for(paux=v[p];paux;paux=paux->urm)
    {	if(!viz[paux->inf])
	{
	   visit(paux->inf);
	   low[p]=(low[p]<low[paux->inf])?low[p]:low[paux->inf];
	}
	else
	low[p]=(low[p]<dsfnum[paux->inf])?low[p]:dsfnum[paux->inf];
    }
    if(low[p]==dsfnum[p])
    {   nc++;
	for(;;)
	{
	  paux=new nod;
	  paux->inf=stiva[top];
	  paux->urm=C[nc];
	  C[nc]=paux;
	  top--;
	  if(stiva[top+1]==p)break;
	}
    }
}
void prints()
{       nod *paux;
	printf("%d",nc);
	for(i=1;i<=nc;i++)
	{ printf("\n");
	  for(paux=C[i];paux;paux=paux->urm)
	   printf("%d ",paux->inf);
	}
	printf("\n");
}