Cod sursa(job #206778)

Utilizator Adriana_SAdriana Sperlea Adriana_S Data 9 septembrie 2008 16:09:35
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.67 kb
#include <stdio.h>
#include <vector>

using namespace std;

const int N_MAX = 100010;

int N, M, nrc;
vector <int> G[N_MAX];
int comp[N_MAX];

void DFS(int nod, int cul)
{
	comp[nod] = cul;
	for (vector <int>::iterator it = G[nod].begin(); it != G[nod].end(); ++ it) {
		if (!comp[*it]) {
			DFS(*it, cul);
		}
	}
}

int main()
{
	freopen("dfs.in", "r", stdin);
#ifndef _SCREEN_
	freopen("dfs.out", "w", stdout);
#endif

	int X, Y;
	scanf("%d %d\n", &N, &M);
	for (int i = 1; i <= M; i ++) {
		scanf("%d %d\n", &X, &Y);
		G[X].push_back(Y);
		G[Y].push_back(X);
	}

	for (int i = 1; i <= N; i ++) {
		if (!comp[i]) {
			nrc ++;
			DFS(i, nrc);
		}
	}

	printf("%d\n", nrc);

	return 0;
}