Cod sursa(job #1704903)

Utilizator perjulucianPerju Lucian Ionut perjulucian Data 19 mai 2016 15:59:44
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.74 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std; 

std::ifstream f("dfs.in");
std::ofstream g("dfs.out");

int N, M;
vector<vector<int>> edges;
vector<bool> visited;

void read(){
	int from,to;
	
	f >> N >> M ;
	
	for(int i = 0 ; i <= N ; ++i){
		edges.push_back(vector<int>());
		visited.push_back(false);
		
	}

	for(int i = 0 ; i < M ; ++i){
		f >> from >> to;
		edges.at(from).push_back(to);
		edges.at(to).push_back(from);
	}
}

void dfs(int nod){
	visited[nod] = true;
	for(auto son : edges.at(nod)){
		if(!visited[son]){
			visited[son] = true;
			dfs(son);
		}
	}
}

void CC(){
	int cc = 0;
	for(int i = 1; i <= N ; ++i){
		if(!visited[i]){
			++cc;
			dfs(i);
		}
	}
	g << cc ;
}


int main(){
	read();
	CC();
	return 0 ;
}