Cod sursa(job #651199)

Utilizator FIIAndCocRotAndrei Alexandra FIIAndCocRot Data 19 decembrie 2011 23:55:24
Problema Sortare topologica Scor 100
Compilator c Status done
Runda Arhiva educationala Marime 1.24 kb
#include<stdio.h>
#include<stdlib.h>
 
#define MAX 50003
 

FILE *f, *g;

 

int N, M, viz[MAX], index, sorttop[MAX], index1;

 

 

typedef struct Node 

{   int info; 

struct Node *next;

} Node;

Node *a[MAX];

 

void file_open ()

{   f=fopen("sortaret.in", "r");

g=fopen("sortaret.out", "w");

}

 

 

void file_close ()

{   fclose (f);

fclose(g);

}

 

int add (int n1, int n2)

{   Node *ptr;

if(!(ptr=(Node*)malloc(sizeof(Node))))

return 0;

ptr->info=n2;

ptr->next=a[n1];

a[n1]=ptr;

return 1;

}

 

void read_node ()

{   int n1, n2;

for(index=0; index<M; index++)

{fscanf(f,"%d%d", &n1, &n2);

if(!(add(n1,n2)))

{printf("eroare");

return ;

}

}

}

 

void write ()

{   for (index=1;index<=N;index++)

fprintf(g, "%d " , sorttop[index]);

}
 

 

void DFS(int S)

{   Node *p;

viz[S]=1;

for(p=a[S]; p!=NULL; p=p->next)
if(viz[p->info]==0)
DFS(p->info);

index1--;

sorttop[index1]=S;

 

}   

 

 

 

int main ()

{   file_open();

fscanf(f,"%d %d", & N, &M);

read_node();

index1=N+1;

for(index=1;index<=N;index++)

if(viz[index]==0)

DFS(index);

write();

file_close();

return 0;

}