Cod sursa(job #1699057)

Utilizator andreibotilaBotila Andrei andreibotila Data 5 mai 2016 22:59:39
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <climits>
#include <string.h>

using namespace std;
const int NMax = 100010;

bool visited[NMax];
vector<int> graf[NMax];

void DFS(int nod) {
	visited[nod] = true;
	int nrNeighbours = graf[nod].size();
	for (int i = 0; i < nrNeighbours; i++) {
		if (!visited[graf[nod][i]]) {
			DFS(graf[nod][i]);
		}
	}
}

int main() {
	int N, M, x, y, nrComponente;
	nrComponente = 0;
	
	ifstream fin ("dfs.in");
	ofstream fout ("dfs.out");

	fin >> N >> M;

	for (int i = 0; i < M; i++) {
		fin >> x >> y;
		graf[x - 1].push_back(y - 1);
		graf[y - 1].push_back(x - 1);
	}

	nrComponente = 0;
	for (int i = 0; i < N; i++) {
		if (!visited[i]) {
			DFS(i);
			nrComponente++;
		}		
	}

	fout << nrComponente;
	return 0;
}