Cod sursa(job #1096511)

Utilizator pulseOvidiu Giorgi pulse Data 2 februarie 2014 10:46:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <cstdio>
#include <vector>

using namespace std;

#define NMAX 100003

int n, m, count = 0;
bool used[NMAX];
vector <int> v[NMAX];

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

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

int main ()
{
	freopen ("dfs.in", "r", stdin);
	freopen ("dfs.out", "w", stdout);
	read_data ();
	for (int i = 1; i <= n; ++i)
	{
		if (!used[i])
		{
			dfs (i);
			++count;
		}
	}
	printf ("%d", count);
	return 0;
}