Cod sursa(job #1699055)

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

using namespace std;
const int NMax = 1000001;

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

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

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;
}