Cod sursa(job #1699054)

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

using namespace std;
const int NMax = 1000001;

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

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

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

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

	fout << nrComponente;
	return 0;
}