Cod sursa(job #146388)

Utilizator MarquiseMarquise Marquise Data 1 martie 2008 17:33:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <stdio.h>

#define NMAX 100001

int N, M, num, viz[NMAX];

struct nod
{
	int info;
	nod *next;
};

nod *m[NMAX];

void adaug(int x, int y)
{
	nod *aux;

	aux = new nod;
	aux -> info = y;
	aux -> next = m[x];
	m[x] = aux;
}


void dfs(int v)
{
	nod *p;

	viz[v] = 1;
	for ( p = m[v]; p; p = p -> next)
		if ( !viz[ p -> info] )
			dfs(p -> info);
}


int main()
{
	int i, x, y;
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	scanf("%d %d", &N, &M);

	for ( i = 1; i <= M; i++)
	{
		scanf("%d %d", &x, &y);
		adaug(x, y);
        adaug(y, x);
	}


	for ( i = 1; i <= N; i++)
		if ( !viz[i])
		{
			dfs(i);
			num++;
		}
	printf("%d\n", num);
	return 0;
}