Cod sursa(job #1176285)

Utilizator cosgbCosmin cosgb Data 25 aprilie 2014 21:00:28
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include <vector>

using namespace std;

void dfs(vector<vector<long> > &lista_ad, vector<bool> &visited, int node_id) {
	visited[node_id] = true;
	for (int i = 0; i < lista_ad[node_id].size(); i++) {
		if (!visited[lista_ad[node_id][i]]) {
			dfs(lista_ad, visited, lista_ad[node_id][i]);
		}
	}
}


int main()
{
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	long comp_conexe = 0, N, id1, id2;
	long long M;

	scanf("%ld%lld", &N, &M);
	
	vector<vector<long> > lista_ad (N + 1, vector<long>(0,0));
	vector<bool> visited(N + 1, false);

	for (int i = 0; i < M; i++) {
		scanf("%ld%ld", &id1, &id2);
		lista_ad[id1].push_back(id2);
		lista_ad[id2].push_back(id1);
	}

	for (int i = 1; i <= N; i++) {
		if (visited[i] == false) {
			++comp_conexe;
			dfs(lista_ad, visited, i);
		}
	}

	printf("%ld\n", comp_conexe);

	return 0;
}