Cod sursa(job #249623)

Utilizator stocarulCosmin-Mihai Tutunaru stocarul Data 28 ianuarie 2009 21:02:47
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.81 kb
#include<stdio.h>
#define infile "dfs.in"
#define outfile "dfs.out"
#define nmax (100*1000+1)
#define mmax (200*1000+1)
char viz[nmax]; //vectorul de vizite, pt a putea face parcurgerea, respectiv pt numararea componentelor conexe
struct lista
	{
	int n,p; //retine nodul, respectiv pozitia nodului anterior care apartine aceluiasi tata
	} l[mmax];
int p[nmax]; //p[i] - retine pozitia din lista a ultimului fiu al nodului i
int n,m; //numarul total de noduri respectiv muchii

//adauga un arc in lista
void add(struct lista l[mmax], int p[nmax], int m, int x, int y)
	{
	int up=p[x]; //pozitia ultimului fiu al lui x
	l[m].n=y; l[m].p=up; //salvam nodul, si pozitia anterioara
	p[x]=m; //salvam si in vectorul de pozitii
	}

void citire(struct lista l[mmax], int p[nmax], int *n, int *m)
	{
	int i,j=0,x,y;
	scanf("%d %d\n",n,m);
	for(i=1;i<=*m;i++)
		{
		scanf("%d %d\n",&x,&y); //avem muchie intre nodurile x si y
		add(l,p,++j,x,y); //arc de la x la y
		add(l,p,++j,y,x); //arc de la y la x
		}
	}

void dfs(struct lista l[mmax], int p[nmax], int n) //n-nod :P
	{
	int up=p[n]; //pozitia ultimului copil din lista
	viz[n]=1; //vizitam nodul
	while(up) //cat timp mai sunt fii inainte
		{
		if(!viz[l[up].n]) //daca nodul nu a fost inca vizitat
			dfs(l,p,l[up].n); //il vizitam
		up=l[up].p; //pozitia nodului anterior
		}
	}

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

citire(l,p,&n,&m); //citim graful si il salvam in lista
int i,k=0;
for(i=1;i<=n;i++) //trecem pe la toate nodurile
	if(!viz[i]) //daca nu a fost vizitat, inseamna ca avem o noua componenta
		{
		dfs(l,p,i); //parcurgem toata componenta
		k++; //crestem numarul total de componente
		}
printf("%d",k); //afisem numarul total de componente conexe

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