Cod sursa(job #1447702)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 5 iunie 2015 00:00:49
Problema Parcurgere DFS - componente conexe Scor 5
Compilator c Status done
Runda Arhiva educationala Marime 1.29 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct{
	int nn;
	int** x;
} TGV, *AGV;

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

int main(){
	freopen("dfs.in", "r", stdin);
	freopen("dfs.out", "w", stdout);
	AGV 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, m);
	if(!graf) return 0;
	
	for(i = 0; i < m; i++){
		scanf("%d%d", &s, &d);
		ins(graf, s, d);
	}
	printf("%d\n", dfs(graf, v));
	return 0;
}

AGV init(int n, int m){
	AGV g = (AGV)malloc(sizeof(TGV));
	if(!g) return NULL;
	
	g->x = (int**)malloc((n + 2) * sizeof(int*));
	if(!g->x){
		free(g);
		return NULL;
	}
	
	g->x[1] = (int*)malloc(m * sizeof(int));
	if(!g->x[1]){
		free(g->x);
		free(g);
		return NULL;
	}

	g->nn = n;
	int i;
	for(i = 2; i <= n + 1; i++)
		g->x[i] = g->x[1];
	
	return g;
}

void ins(AGV g, int s, int d){
	if(s > g->nn) return;
	*g->x[s + 1] = d;
	int i;
	for(i = s + 1; i <= g->nn + 1; i++)
		g->x[i]++;
}

void auxdfs(AGV g, int a, int* v){
	int* i;
	if(v[a]) return;
	v[a] = 1;
	for(i = g->x[a]; i < g->x[a + 1]; i++)
		auxdfs(g, *i, v);
}

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

	return cnt;
}