Cod sursa(job #2501676)

Utilizator CyborgSquirrelJardan Andrei CyborgSquirrel Data 30 noiembrie 2019 09:33:59
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.53 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

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

vector<int> gr[100041];
bool vi[100041];
void dfs(int a){
	vi[a] = 1;
	for(auto b : gr[a]){
		if(!vi[b]){
			dfs(b);
		}
	}
}

int main(){
	int n, m;
	fin >> n >> m;
	for(int i = 0; i < m; ++i){
		int a, b;fin >> a >> b;
		gr[a].push_back(b);
		gr[b].push_back(a);
	}
	
	int s = 0;
	for(int i = 1; i <= n; i++){
		if(!vi[i]){
			dfs(i);
			s++;
		}
	}
	fout << s;
	return 0;
}