Cod sursa(job #650859)

Utilizator FIIGLMFIIGherasimLupascuMiron FIIGLM Data 19 decembrie 2011 00:47:05
Problema Sortare topologica Scor 0
Compilator c Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
        int info;
        struct node *next;
        } node;
node *L[100001];

int length,viz[50001],postordine[50001],N,M;

void DFS(int x)
 {
      viz[x]=1;
      node* p;
	if(!(p=(node*)calloc(1,sizeof(node)))) 
		return;
	for(p=L[x];p!=NULL;p=p->next)
		if(!viz[p->info])
			DFS(p->info);
	length++;
	postordine[length]=x;
}

int main()
{
	int i,j,k;
	node *p;
	FILE *fin,*fout;
	fin=fopen("sortaret.in","r");
	fout=fopen("sortaret.out","w");

	fscanf(fin,"%d %d",&N,&M);
    	for(k=1;k<=M;k++)
    	{
		fscanf(fin,"%d %d",&i,&j);
   		 p=(node*)calloc(1,sizeof(node));  //se adauga j in lista vecinilor lui i 
   		 p->info=j;
   		 p->next=L[i];
  		 L[i]=p;
    	}
	fclose(fin);
	
	for(i=1;i<=N;i++)
		if(!viz[i])
			DFS(i);
	for(i=N;i>=1;i--)
	fprintf(fout,"%d ",postordine[i]);



  system("PAUSE");	
  return 0;
}