Cod sursa(job #796811)

Utilizator noctavianNastasie Ion Octavian noctavian Data 12 octombrie 2012 17:11:10
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	int *vec;
	int nvec;
} state;

void add(state* viz, int a, int b) {
	viz[a].vec = (viz[a].nvec == 0 ? (int*)malloc(sizeof(int)) : (int*)realloc(viz[a].vec,(viz[a].nvec + 1)*sizeof(int)));
	viz[a].vec[viz[a].nvec] = b;
	viz[a].nvec++;
}

void vizit(int* viz, state* vizy, int nod, FILE *fis) {
	int i;
	for(i = 0; i < vizy[nod].nvec; i++) {
		if(viz[vizy[nod].vec[i]] == 0) {
			viz[vizy[nod].vec[i]] = 1;
			vizit(viz, vizy, vizy[nod].vec[i], fis);
			fprintf(fis, "%i ", vizy[nod].vec[i]);
		}
	}
}

int main() {
	int x, y, N, M, i, *viz;
	state *vizx, *vizy;
	FILE *fis;

	fis = fopen("sortaret.in", "rt");
	fscanf(fis, "%i %i", &N, &M);
	vizy = (state*)calloc(N+1, sizeof(state));
	viz = (int*)calloc(N+1, sizeof(int));

	for(i = 0; i < M; i++) {
		fscanf(fis, "%i %i", &x, &y);
		add(vizy, y, x);
	}
	fclose(fis);
	
	fis = fopen("sortaret.out","wt");
	for(i = 1; i <= N; i++)
		if(viz[i] == 0) {
			viz[i] = 1;
			vizit(viz, vizy, i, fis);
			fprintf(fis,"%i ", i);
		}
	fclose(fis);

	free(viz);
	free(vizy);
	return 0;
}