Cod sursa(job #1451584)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 17 iunie 2015 19:32:17
Problema Parcurgere DFS - componente conexe Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.38 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct cel{
	int info;
	struct cel* urm;
} TCel, *TLista, **ALista;

typedef struct{
	int nn;
	ALista x;
} TGL, *AGL;

AGL init(int n);
void ins(AGL g, int s, int d);
void auxdfs(AGL g, int a, int* v);
int dfs(AGL g, int* v);

int main(){
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	AGL graf;
	int n, m, i, s, d;
	int *v;
	scanf("%d%d", &n, &m);
	v = (int*)calloc(n + 1, sizeof(int));
	if(!v) return 0;
	graf = init(n);
	if(!graf) return 0;
	
	for(i = 0; i < m; i++){
		scanf("%d%d", &s, &d);
		ins(graf, s, d);
	}
//afis(graf);
	printf("%d\n", dfs(graf, v));
	free(v);
	return 0;
}

AGL init(int n){
	AGL g = (AGL)malloc(sizeof(TGL));
	if(!g) return NULL;

	g->x = (ALista)calloc(n + 1, sizeof(TLista));
	if(!g->x){
		free(g);
		return NULL;
	}

	g->nn = n;
	return g;
}

void ins(AGL g, int s, int d){
	TLista aux1 = (TLista)malloc(sizeof(TCel));
	if(!aux1) return;
	aux1->info = d;
	aux1->urm = g->x[s];
	g->x[s] = aux1;

	TLista aux2 = (TLista)malloc(sizeof(TCel));
  if(!aux2) return;
  aux2->info = s;
  aux2->urm = g->x[d];
	g->x[d] = aux2;
}

void auxdfs(AGL g, int a, int* v){
	if(v[a]) return;
//printf("%d\n", a);
	v[a] = 1;
	TLista l = g->x[a];
	while(l){
		auxdfs(g, l->info, v);
		l = l->urm;
	}
}

int dfs(AGL g, int* v){
	int i, cnt = 0;
	for(i = 1; i <= g->nn; i++)
		if(!v[i]){
			cnt++;
			auxdfs(g, i, v);
		}
	
	return cnt;
}