Cod sursa(job #484681)

Utilizator edward_alexStanciu Alexandru Marian edward_alex Data 15 septembrie 2010 12:13:30
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.11 kb
#include<stdio.h>
#include<stdlib.h>

typedef struct nod{
	int info;
	struct nod *next;
}nod;

nod *a[1000009];

void adauga(int x,nod **u){
    nod *nou = (nod*)malloc(sizeof(nod));
    nod *ultim = *u;
    nou->info = x;
    nou->next = ultim;
    *u = nou;
}

void dfs(int x,int *v,nod **u){
	nod *q;
	v[x] = 1;
	int y;
	for(q = a[x];q != NULL;q = q->next){
		y = q->info;
		if(v[y] == 0)
			dfs(y,v,u);
	}
	adauga(x,u);
}

void afis_stiva(nod *u){
	FILE *g = fopen("sortaret.out","w");
	while(u != NULL){
		fprintf(g,"%d ",u->info);
		u = u->next;
	}
	fclose(g);
}

void free_stiva(nod *u){
	nod *aux;
	while(u != NULL){
		aux = u;
		u = u->next;
		free(aux);
	}
}

int main(){
	FILE *f;
	f = fopen("sortaret.in","r");
	int i,n,m,k1,k2;
	fscanf(f,"%d%d",&n,&m);
	for(i = 1;i <= n;i++)
		a[i] =NULL;
	for(i = 0;i < m;i++){
		fscanf(f,"%d%d",&k1,&k2);
		adauga(k2,&a[k1]);
	}
	int *v = (int*)calloc((n + 1),sizeof(int));
	nod *u = NULL;
	for(i = 1;i <= n;i++)
		if(v[i] == 0)
			dfs(i,v,&u);
	afis_stiva(u);
	free_stiva(u);
	//free_lista(a,n);
	free(v);
	fclose(f);
	return 0;
}