Cod sursa(job #160227)

Utilizator gigi_becaliGigi Becali gigi_becali Data 14 martie 2008 21:28:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.71 kb
#include <cstdio>
#include <cstdlib>
#define N 100001

int *a[N];
int n;
int use[N];

inline void dfs(int n)
{
	if(use[n]) return ;
	use[n]=1;
	
	int i;
	for(i=1;i<=a[n][0];++i)
		if(!use[a[n][i]])
			dfs(a[n][i]);
}

int main()
{
	int m,p,q;
	
	freopen("dfs.in","r",stdin);
	scanf("%d %d\n", &n, &m);
	for(int i=1;i<=n;++i) a[i]=new int[2], a[i][0]=0;
	
	while(m--)
	{
		scanf("%d %d\n", &p, &q);
		a[p]=(int*)realloc(a[p], sizeof(int)*(a[p][0]+2));
		a[q]=(int*)realloc(a[q], sizeof(int)*(a[q][0]+2));
		a[p][++a[p][0]]=q;
		a[q][++a[q][0]]=p;
		
		
	}
	int nr=0;
	for(int i=1;i<=n;++i)
		if(!use[i]){++nr; dfs(i);}
	
freopen("dfs.out","w",stdout);		
	printf("%d\n", nr);
	return 0;
}