Cod sursa(job #1834794)

Utilizator flibiaVisanu Cristian flibia Data 25 decembrie 2016 11:06:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.47 kb
#include <bits/stdc++.h>

using namespace std;

vector <int> v[100005]; int n, m, a, b, k; bool s[100005];

void dfs(int k){
	s[k] = 1;
	for(int j = 0; j < v[k].size(); j++)
		if(!s[v[k][j]]) dfs(v[k][j]);
}

int main(){
	ifstream in("dfs.in");
	ofstream out("dfs.out");
	in >> n >> m;
	for(int i = 1; i <= m; i++){
		in >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for(int i = 1; i <= n; i++)
		if(!s[i]) k++, dfs(i);
	out << k;
	return 0;
}