Cod sursa(job #412274)

Utilizator b_polarAgape Mihai b_polar Data 5 martie 2010 14:17:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.49 kb
#include <stdio.h>
#include <stack>
#define infile "ctc.in"
#define outfile "ctc.out"
#define NMAX 100005
using namespace std;

typedef struct snod{int x;snod *nxt;}*L;
L G[NMAX],GT[NMAX],CMP[NMAX];
stack <int> stiva;
int vizitat[NMAX],N,M,NCMP;

void add(int,int,L*),citire(),rezolvare(),afisare();

int main()
{
	freopen(infile,"r",stdin);
	freopen(outfile,"w",stdout);
	
	citire();
	rezolvare();
	afisare();
}

void afisare()
{
	printf("%d\n",NCMP);
	for(int i=1;i<=NCMP;i++)
	{
		for(L p=CMP[i];p;p=p->nxt)
			printf("%d ",p->x);
		printf("\n");
	}
}


//rezolvarea problemei - parcurgerile DF

void DF1(int nod)
{
	vizitat[nod]=1;
	for(L p=G[nod];p;p=p->nxt)
		if(!vizitat[p->x])DF1(p->x);
	stiva.push(nod);
}

void DF2(int nod,int k)
{
	//printf("%d ",nod);
	add(k,nod,CMP);
	vizitat[nod]=1;
	for(L p=GT[nod];p;p=p->nxt)
		if(!vizitat[p->x])DF2(p->x,k);
}

void rezolvare()
{
	//prima parcurgere
	int i;
	for(i=1;i<=N;i++)
		if(!vizitat[i])DF1(i);
	
	//reinitializam vectorul vizitat[] cu 0
	for(i=1;i<=N;i++)vizitat[i]=0;
		
	//a doua parcurgere - pe graful transpus
	for(i=1;!stiva.empty();stiva.pop())
	{
		int nod=stiva.top();
		if(!vizitat[nod])
			DF2(nod,i++);
	}
	NCMP=i-1;
}

//citirea din fisier
void citire()
{
	int i,s,d;
	scanf("%d %d",&N,&M);
	for(i=1;i<=M;i++)
	{
		scanf("%d %d",&s,&d);
		add(s,d,G);
		add(d,s,GT);
	}
}

void add(int a,int b,L *g)
{
	L aux=new snod;
	aux->x=b;
	aux->nxt=g[a];
	g[a]=aux;
}