Cod sursa(job #2670318)

Utilizator etohirseCristi Cretu etohirse Data 9 noiembrie 2020 17:54:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.58 kb
#include <fstream>
#include <vector>

std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");

const int mxN = 1e5 + 5;

int n, m, ans;
bool viz[mxN];
std::vector < int > mat[mxN];

void DFS(int Nod){
	viz[Nod] = 1;
	for(unsigned i = 0; i < mat[Nod].size(); ++i){
		int vecin = mat[Nod][i];
		if (!viz[vecin]) DFS(vecin);
	}
}
void solve(){
	fin >> n >> m;
	for (int i = 1; i <= m; ++i){
		int a, b;
		fin >> a >> b;
		mat[a].push_back(b), mat[b].push_back(a);
	}
	for (int i = 1; i <= n; ++i){
		if (!viz[i]){
			ans++;
			DFS(i);
		}
	}
}

int main(){
	solve();
	fout << ans;
	return 0;
}