Cod sursa(job #562162)

Utilizator AndreiRSStatescu Andrei Rares AndreiRS Data 22 martie 2011 15:12:38
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <stdio.h>
#include <vector>
using namespace std;
const int DIM = 100001;

int N, M, viz[DIM], L[DIM], C;
vector <int> V[DIM];

void dfs (int n)
{
	viz[n] = 1;
	for (int i = 0; i < L[n]; i++)
		if ( !viz[V[n][i]] )
			dfs (V[n][i]);	
}

int main ()
{
	freopen ("dfs.in", "r", stdin);
	freopen ("dfs.out", "w", stdout);
	
	scanf ("%d%d", &N, &M);
	for (int i = 0, a, b; i < M; i++)
	{
		scanf ("%d%d", &a, &b);
		V[a].push_back (b);
		V[b].push_back (a);
	}
	
	for (int i = 1; i <= N; i++)
		L[i] = V[i].size ();
	
	for (int i = 1; i <= N; i++)
		if ( !viz[i] )
		{
			C++;
			dfs (i);
		}

	printf ("%d", C);
	return 0;
}