Cod sursa(job #238795)

Utilizator ilincaSorescu Ilinca ilinca Data 3 ianuarie 2009 12:24:55
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <stdio.h>
#include <vector>

#define nmax 100005
#define pr(x) fprintf(stderr,#x" = %d\n",x)

using namespace std;

int n, m;

vector <bool> viz (nmax, false);
vector < vector <int> > v (nmax);

void scan ()
{
	int a, b;
	scanf ("%d%d", &n, &m);
	for (int i=1; i<=m; ++i)
	{
		scanf ("%d%d", &a, &b);
		v [a].push_back (b);
		v [b].push_back (a);
	}
}

void dfs (int x)
{
	viz [x]=true;
	for (vector <int>::iterator it=v [x].begin (); it != v [x].end (); ++it)
		if (viz [*it] == false)
			dfs (*it);
}

int res ()
{
	int num=0;
	for (int i=1; i<=n; ++i)
		if (viz [i] == false)
		{
			++num;
			dfs (i);
		}
	return num;
}

int main ()
{
	freopen ("dfs.in", "r", stdin);
	freopen ("dfs.out", "w", stdout);
	scan ();
	printf ("%d\n", res ());
	return 0;
}