Cod sursa(job #1458283)

Utilizator glbglGeorgiana bgl glbgl Data 7 iulie 2015 11:54:07
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>
#include <vector>
#include <fstream>
#include <iostream>


using namespace std;


int N, M, count = 0;
vector< vector<int> > neigh;
vector<bool> visited;

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



void read(){

	in >> N >> M;

	for(int i = 0; i <= N; ++i){
		vector<int> v;
		neigh.push_back(v);
	}

	visited.resize(N+1);

	int x, y;

	for(int i = 0; i < M; ++i){
		in >> x >> y;
		neigh[x].push_back(y);
		neigh[y].push_back(x);
	}
}


void DFS(int u){
	
	visited[u] = true;
	for(unsigned int i = 0; i < neigh[u].size(); ++i){
		int v = neigh[u][i];
		if(visited[v] == false)
			DFS(v);
	}
	
}


void ComponenteConexe(){

	for(int i = 1; i <= N; ++i){
		if(visited[i] == false){
			count++;
			DFS(i);
		}
	}
}


int main(){

	read();
	ComponenteConexe();
	out << count;
}