Cod sursa(job #1402741)

Utilizator diac_paulPaul Diac diac_paul Data 26 martie 2015 19:33:11
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <vector>

#define NMax 100001
#define MMax 200000

using namespace std;

FILE *fin = fopen("dfs.in", "rt");
FILE *fout = fopen("dfs.out", "wt");

int N, M;
vector<int> v[NMax];

int vizitat[NMax];

void goDFS(int node) {
	vizitat[node] = 1;
	for (int i = 0; i < v[node].size(); i++) {
		if (!vizitat[v[node][i]]) {
			goDFS(v[node][i]);
		}
	}
}

int main() {

	fscanf(fin, "%d %d", &N, &M);

	int x, y;
	for (int i = 0; i < M; i++) {
		fscanf(fin, "%d %d", &x, &y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	
	// d[] a revenit la valoarea dinainte de resetare
	int nrConexe = 0; // numar componente conexe
	for (int i = 1; i <= N; i++) {
		if (!vizitat[i]) {
			goDFS(i);
			nrConexe++;
		}
	}

	fprintf(fout, "%d\n", nrConexe);

	fclose(fin);
	fclose(fout);
	return 0;
}