Cod sursa(job #148420)

Utilizator crawlerPuni Andrei Paul crawler Data 4 martie 2008 12:17:22
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <stdio.h>
#include <stdlib.h>

#define Nmax 100100

int *l[Nmax], v[Nmax], n, m;

void DF(int nod)
{
	v[nod] = 1;
	for (int i=1;i<=l[nod][0];++i)
        if (v[l[nod][i]] == 0) DF(l[nod][i]);
}

int main()
{
	freopen("dfs.in","r",stdin);
	freopen("dfs.out","w",stdout);

	scanf("%d%d", &n,&m);

	int i,x,y,cnt=0;

	for (i=1;i<=n;++i)
	{
		l[i] = (int*)realloc(l[i],sizeof(int));
		l[i][0] = 0;
	}

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

	for (i=1;i<=n;++i)
	if (v[i] == 0)
	{
		++cnt;
		DF(i);
	}

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


	return 0;
}