Cod sursa(job #1402727)

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

#define NMax 100001
#define MMax 200000

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

int N, M;
int * v[NMax];
int d[NMax];

int x[MMax], y[MMax];

int vizitat[NMax];

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

int main() {

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

	for (int i = 0; i < M; i++) {
		fscanf(fin, "%d %d", &x[i], &y[i]);
		d[x[i]]++;
		d[y[i]]++;
	}

	for (int i = 1; i <= N; i++) {
		v[i] = (int *) malloc(d[i] * sizeof(v[0][0]));
		d[i] = 0;
	}

	for (int i = 0; i < M; i++) {
		
		// d[x[i]] reprezinta cati vecini ai nodului x[i] au fost pusi deja in lista de adiacenta
		// de exemplu daca x[i] == 7, si daca d[x[i]] == 2, am deja pusi cate un vecin pe v[7][0] si v[7][1]; deci voi pune pe v[7][2]
		v[ x[i] ][ d[x[i]] ] = y[i];
		d[x[i]]++;

		v[ y[i] ][ d[y[i]] ] = x[i];
		d[y[i]]++;
	}

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