Cod sursa(job #1483779)

Utilizator DacianBocea Dacian Dacian Data 9 septembrie 2015 21:56:46
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.45 kb
#include <fstream>
#include <vector>

int v[100020];
std::vector<int> g[100020];

void dfs(int i){
	v[i] = 1;
	for (auto d : g[i]){
		if (!v[d]) dfs(d);
	}
}

int main(){
	std::ifstream f("dfs.in");
	std::ofstream c("dfs.out");
	int a, b, n, m, Nr = 0;
	f >> n >> m;
	for (int i = 0; i < m; ++i) { f >> a >> b; g[a].push_back(b); g[b].push_back(a); }
	for (int i = 1; i <= n; ++i)
		if (!v[i]){ Nr++; dfs(i); }
	c << Nr << '\n';
	return 0;
}