Cod sursa(job #500908)

Utilizator skullLepadat Mihai-Alexandru skull Data 13 noiembrie 2010 16:53:28
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;
#define nmax 100005

int n, count;
int viz[nmax];
vector<int> G[nmax];

void citire ()
{
	int i, m, x, y;
	freopen("dfs.in","r",stdin);
	scanf("%d%d", &n, &m);
	for (i = 1; i <= m; ++i)
	{
		scanf("%d%d", &x, &y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
}

void dfs ( int x )
{
	int i;
	viz[x] = 1;
	for (i = 0; i < G[x].size (); ++i)
		if ( !viz[G[x][i]] ) dfs(G[x][i]);
}

void solve ()
{
	int i;
	for (i = 1; i <= n; ++i)
		if ( !viz[i] ) { dfs(i); count++; }
	freopen("dfs.out","w",stdout);
	printf("%d", count);
}

int main ()
{
	citire ();
	solve ();
	return 0;
}