Cod sursa(job #218957)

Utilizator ada_sAda-Mihaela Solcan ada_s Data 4 noiembrie 2008 14:00:53
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include <stdio.h>
const long N=100000;
long *a[N], x[N], y[N], d[N], viz[N];

void dfs(int x);

int main()
{
	long i, conex=0, n, m;
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	scanf("%ld%ld", &n, &m);
	for (i=0; i<n; i++)
	{
		scanf("%ld%ld", &x[i], &y[i]);
		d[x[i]]++;
		d[y[i]]++;
	}//for i
	for (i=0; i<n; i++)
	{
		a[i]=new long[d[i]+1];
		a[i][0]=0;
	}//for i
	for (i=0; i<n; i++)
	{
		a[y[i]][++a[y[i]][0]]=x[i];
		a[x[i]][++a[x[i]][0]]=y[i];
	}//for i
	for (i=0; i<n; i++)
		if (!viz[i])
		{
			conex++;
			dfs(i);
		}//if
	printf("%ld", conex);	
}//main

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