Cod sursa(job #148944)

Utilizator peanutzAndrei Homorodean peanutz Data 5 martie 2008 00:15:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define NMAX 100010

typedef struct nod
{
	long v;
	nod *urm;
} *pnod;

pnod l[NMAX];
char uz[NMAX];
long n, m;
long nr;


inline void add(long x, long y)
{
	pnod aux;
	aux = new nod;

	aux -> v = y;
	aux -> urm = l[x];
	l[x] = aux;
}


void read()
{
	long i, x, y;

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

	for(i = 1; i <= m; ++i)
	{
		scanf("%ld %ld", &x, &y);

		add(x, y);
		add(y, x);
	}
}


long c[NMAX];


void bf(long x)
{
	long inc, sf;
	long i;
	pnod it;

	inc = sf = 1;
	c[1] = x;
	++uz[x];

	while(inc <= sf)
	{
		x = c[inc++];


		for(it = l[x]; it != NULL; it = it -> urm)
		{
			i = it -> v;

			if(!uz[i])
			{
				++uz[i];
				c[++sf] = i;
			}
		}
	}
}


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

	read();

	for(i = 1; i <= n; ++i)
		if(!uz[i])
		{
			++nr;
			bf(i);
		}

	printf("%ld\n", nr);

	return 0;
}