Cod sursa(job #148727)

Utilizator alecmanAchim Ioan Alexandru alecman Data 4 martie 2008 19:34:19
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.25 kb
#include<stdio.h>
#include<string.h>

#define INPUT "sortaret.in"
#define OUTPUT "sortaret.out"
#define CL(x) memset(x,0,sizeof(x));

FILE *fin=fopen(INPUT, "r"),*fout=fopen(OUTPUT, "w");

typedef struct elem{
  long value;
  struct elem *next;
};

elem* p[50001];
elem* r;

long n,m;
char util[50001];

void readValues();

void solveFunction();

void DF(long);

void printSolution();

int main(){
  readValues();
  solveFunction();
  fclose(fin);
  fclose(fout);
  return 0;
}

void readValues(){
  fscanf(fin, "%ld %ld", &n, &m);
  elem *adr;
  long val1,val2;
  for(long i=1;i<=m;++i){
    fscanf(fin, "%ld %ld", &val1, &val2);
    adr=new elem;
    adr->value = val2;
    adr->next = p[val1];
    p[val1] = adr;
  }
}

void solveFunction(){
  CL(util);
  for(long i=1;i<=n;++i){
    if(!util[i])
      DF(i);
  }
  printSolution();
}

void DF(long val){
  elem *adr;
  util[val]=1;
  adr=p[val];
  while(adr!=NULL){
    if(!util[adr->value])
      DF(adr->value);
    adr=adr->next;
  }
  adr=new elem;
  adr->value=val;
  adr->next=r;
  r=adr;
}

void printSolution(){
  elem *adr;
  adr=r;
  while(adr!=NULL){
    fprintf(fout, "%ld ", adr->value);
    adr=adr->next;
  }
  fprintf(fout, "\n");
}