Cod sursa(job #328756)

Utilizator ooctavTuchila Octavian ooctav Data 3 iulie 2009 12:21:52
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
// dfs.cpp : Defines the entry point for the console application.
//

#include <cstdio>
#include <cstring>
#include <map>
#include <list>
#include <deque>
#include <cstdlib>
int *e[100001];
int viz[100001];
int n,m;
int x,y,c=0;

void citire()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		e[i]=(int *)realloc(e[i],sizeof(int));
		e[i][0]=0;
	}
	for(int i=1;i<=m;i++)
	{
		scanf("%d %d",&x,&y);
		e[x][0]++;
		e[x]=(int *)realloc(e[x],sizeof(int)*(e[x][0]+1));
		e[x][e[x][0]]=y;
		e[y][0]++;
		e[y]=(int *)realloc(e[y],sizeof(int)*(e[y][0]+1));
		e[y][e[y][0]]=x;
	}

}

void dfs(int a)
{
	viz[a]=1;
	for(int i=1;i<=e[a][0];i++)
		if(!viz[e[a][i]])
			dfs(e[a][i]);
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);
	citire();
	for(int i=1;i<=n;i++)
		if(!viz[i])
		{
			dfs(i);
			c++;
		}

	printf("%d",c);


	return 0;
}