Cod sursa(job #2213216)

Utilizator cyg_Miky2003Dancaescu Mihai cyg_Miky2003 Data 15 iunie 2018 19:37:35
Problema Parcurgere DFS - componente conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>
#include <vector>
#include <fstream>
#include <iostream>

#define MAX 100000

using namespace std;


int N, M, count = 0;
vector<int> neigh[MAX+1];
vector<bool> visited(MAX+1);




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



void read(){

	in >> N >> M;

	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;