Cod sursa(job #1329919)

Utilizator MarianMMorosac George Marian MarianM Data 29 ianuarie 2015 23:50:27
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#define _CRT_SECURE_NO_DEPRECATE

#include <iostream>
#include <vector>
using namespace std;

#define DMAX 100002

int N, M, nrCC;

struct Nod{
	int used, dpth;
	vector<int> Adj;
}G[DMAX];

void DFS(int root){
	int i, lg = G[root].Adj.size(), d = G[root].dpth, child;

	G[root].used = 1;

	for (i = 0; i < lg; i++){
		child = G[root].Adj[i];
		if (!G[child].used){
			G[child].dpth = d + 1;
			DFS(child);
		}
	}
}

int main(){
	int i, j, x, y;

	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);

	scanf("%d %d", &N, &M);

	for (i = 1; i <= M; i++){
		scanf("%d %d", &x, &y);
		G[x].Adj.push_back(y);
		G[y].Adj.push_back(x);
	}

	for (i = 1; i <= N; i++){
		if (!G[i].used){
			nrCC++;
			DFS(i);
		}
	}

	printf("%d", nrCC);

	return 0;
}