Cod sursa(job #249997)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 29 ianuarie 2009 19:39:33
Problema Componente tare conexe Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 2.06 kb
#include<stdio.h>
#define infile "ctc.in"
#define outfile "ctc.out"
#define nmax (100*1000+1)
#define mmax (200*1000+1)
struct lista
	{
	int n,p; //nodul ce il reprezinta, respectiv pozitia unui nod anterior
	};
struct lista l[mmax]; int p[nmax]; char viz[nmax]; //graful normal
struct lista lt[mmax]; int pt[nmax]; char vizt[nmax]; //graful TRANSPUS
int post[nmax], postt[nmax]; //vectorul de postordine....se realizeaza la prima parcurgere....am facut doi vectori, deoarece folosim aceeasi functie de parcurgere....al 2-lea vector NU NE INTERESEAZA
int n,m; //numarul de noduri respectiv muchii
int k; //numarul de componente tare conexe

//adauga arc de la x la y
void add(struct lista l[mmax], int p[nmax], int m, int x, int y)
	{
	l[m].n=y; l[m].p=p[x]; p[x]=m; //adaugam nodul in lista...si actualizam pe p[x]
	}

void citire(struct lista l[mmax], int p[nmax], struct lista lt[mmax], int pt[nmax], int *n, int *m)
	{
	int i,x,y;
	scanf("%d %d",n,m);
	for(i=1;i<=*m;i++)
		{
		scanf("%d %d\n",&x,&y);
		add(l,p,i,x,y); //adaugam nodul arc pt graful normal
		add(lt,pt,i,y,x); //adaugam muchia inversa (pt graful transpus)
		}
	}

void dfs(struct lista l[mmax], int p[nmax], int post[nmax], char viz[nmax], int n) //n-nodul din care facem aprcurgerea
	{
	viz[n]=1; //vizitam nodul
	int ul=p[n]; //aflam pozitia ultimului copil
	while(ul) //cat timp are frasti anteriori
		{
		if(!viz[l[ul].n]) //daca nu a mai fost vizitat
			dfs(l,p,post,viz,l[ul].n); //il vizitam
		ul=l[ul].p; //pozitia unui frate anterior
		}
	post[++post[0]]=n; //am parcurs in adancime toti copii....deci il bifam si pe el
	}

int main()
{
int i;
freopen(infile,"r",stdin);
freopen(outfile,"w",stdout);

citire(l,p,lt,pt,&n,&m);

//facem parcurgerea normala
for(i=1;i<=n;i++)
	if(!viz[i]) dfs(l,p,post,viz,i); //nu a fost bifat....il parcurgem

//facem parcurgerea in graful transpus
for(i=n;i>0;i--)
	if(!vizt[post[i]])
		{
		k++; //marcam ca am gasit o componenta
		dfs(lt,pt,postt,vizt,post[i]);
		}

printf("%d\n",k);

fclose(stdin);
fclose(stdout);
return 0;
}