Cod sursa(job #1402738)

Utilizator diac_paulPaul Diac diac_paul Data 26 martie 2015 19:31:18
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.31 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 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);

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

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

	fin = fopen("dfs.in", "rt");
	fscanf(fin, "%d %d", &N, &M);

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

		// 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 ][ d[x] ] = y;
		d[x]++;

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

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