Cod sursa(job #496608)

Utilizator PlayLikeNeverB4George Marcus PlayLikeNeverB4 Data 29 octombrie 2010 22:17:56
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.48 kb
#include <stdio.h>

const int maxn=100001;
struct nod {
	int inf;
	nod *next;
} *A[maxn],*Sol[maxn];

int i,N,M, ind[maxn],inS[maxn],lowlink[maxn],st[2*maxn],NR,k,index;
void citire()
{
	int x,y;
	scanf("%d %d",&N,&M);
	for(i=1;i<=M;i++)
	{
		scanf("%d %d",&x,&y);
		nod *q=new nod;
		q->inf=y;
		q->next=A[x];
		A[x]=q;
	}
}

int min(int a, int b)
{
	if(a<b) return a;
	return b;
}
void tarjan(int p)
{
	ind[p]=index; // al catelea e elementul in arborele DFS
	lowlink[p]=index; // specific alg Tarjan
	index++;
	st[++k]=p; inS[p]=1; // introducem in stiva si marcam ca introdus
	for(nod *x=A[p];x;x=x->next) //verificam toti vecinii
	{
		if(ind[x->inf]==0) //daca nu e vizitat
		{
			tarjan(x->inf); // il vizitam
			lowlink[p]=min(lowlink[p],lowlink[x->inf]); //... teorie
		}
		else 
			if(inS[x->inf]) //daca e deja in stiva
				lowlink[p]=min(lowlink[p],ind[x->inf]);//... -"-
	}
	    if(lowlink[p] == ind[p]) //... -"-
		{
			NR++; //marim numarul componentelor tare conexe
			do // adaugam la solutie
			{
			    nod *s=new nod;
				s->inf=st[k];
				s->next=Sol[NR];
				Sol[NR]=s;
				inS[st[k]]=0;
			}
			while(st[k--]!=p);
		}
}

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("ctc.in","r",stdin);
	freopen("ctc.out","w",stdout);
	citire();
	index=1;
	for(i=1;i<=N;i++)
		if(ind[i]==0) tarjan(i);
	afisare();
}