Cod sursa(job #1237120)

Utilizator ELHoriaHoria Cretescu ELHoria Data 3 octombrie 2014 10:13:06
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <fstream>
#include <vector>

using namespace std;

void dfs(const int& v,const vector< vector<int> >& graph, vector<bool>& visited) {
	visited[v] = true;
	for (const int& w : graph[v]) {
		if (!visited[w]) {
			dfs(w, graph, visited);
		}
	}
}

int main() {
	ifstream cin("dfs.in");
	ofstream cout("dfs.out");
	int n, m;
	cin >> n >> m;
	vector< vector< int > > graph(n);
	vector<bool> visited(n);
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		x--, y--;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	
	int ans = 0;
	for (int i = 0; i < n; i++) {
		if (!visited[i]) {
			ans++;
			dfs(i, graph, visited);
		}
	}
	cout << ans;
	return 0;
}