Cod sursa(job #2202117)

Utilizator caiaandrei14Caia Andrei caiaandrei14 Data 7 mai 2018 17:00:53
Problema Parcurgere DFS - componente conexe Scor 10
Compilator c Status done
Runda Arhiva educationala Marime 1.26 kb
#include <stdio.h>
#include <stdlib.h>
#define Max 100000

int n, m, viz[Max], nr;
int *adia[Max];

void initializare();

void citire();

void dfs(int s);

void afisare();

void componente_conexe();
int main(){

	citire();
	//afisare();
	componente_conexe();
	return 0;
}

void citire(){

	FILE* f = fopen("dfs.in", "r");
	fscanf(f, "%d%d", &n, &m);
	int x, y;
	for(int i = 1; i <= n; i++){
		adia[i] = (int* )realloc(adia[i], sizeof(int));
		adia[i][0] = 0;
	}
	for(int i = 0; i < m; i++){
		fscanf(f, "%d%d", &x, &y);
		adia[x][0]++;
		adia[x] = (int* )realloc(adia[x], (adia[x][0])*sizeof(int));
		adia[x][adia[x][0]] = y;
		adia[y][0]++;
		adia[y] = (int* )realloc(adia[y], (adia[y][0])*sizeof(int));
		adia[y][adia[y][0]] = x;
	}
	fclose(f);

}

void initializare(){
	for(int i = 1; i <= Max; i++)
		viz[i] = 0;
}

void dfs(int s){
	int i;
	//printf("%d ", s);
	viz[s] = 1;
	for(i = 1; i <= adia[s][0]; i++)
		if(!viz[adia[s][i]])
			dfs(adia[s][i]);
}

void afisare(){
	FILE* f = fopen("dfs.out", "w");
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= adia[i][0]; j++)
			fprintf(f, "%d ", adia[i][j]);
		fprintf(f, "\n");
	}
}

void componente_conexe(){
	for(int i = 1; i <= n; i++)
		if(viz[i] == 0){
			nr++;
			dfs(i);
		}

	FILE* f = fopen("dfs.out", "w");
	fprintf(f, "%d", nr);
}