Cod sursa(job #1519353)

Utilizator MesesanPaulMesesanPaul MesesanPaul Data 7 noiembrie 2015 11:24:20
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include <iostream>
#include <vector>
#include <fstream>

using namespace std;

ifstream file_read("dfs.in");
ofstream file_write("dfs.out");

const int maxn=100005;

int n,m, cntConexe;
vector <int> g[maxn];
bool vizitat[maxn];

void dfs(int node){
	vizitat[node]=1;
	for(int i=0;i< int(g[node].size());++i){
		int vecin = g[node][i];
		if(!vizitat[vecin]){
			dfs(vecin);
		}
	}
}

int main(){
	int x, y;

	file_read >>n >>m;
	for(int i=1;i<=m;++i){
		file_read >>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	
	for(int i=1;i<=n;++i){
		if(!vizitat[i]){
			++cntConexe;
			dfs(i);
		}
	}
	file_write <<cntConexe;
	
	file_read.close();
	file_write.close();
	return 0;
}