Cod sursa(job #227113)

Utilizator drag0shSandulescu Dragos drag0sh Data 3 decembrie 2008 18:35:47
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
FILE *f=fopen("sortaret.in","r"),*g=fopen("sortaret.out","w");

#define ALB 0
#define GRI 1
#define NEGRU 2
#define NMAX 50005

struct nod{
  int vf;
  nod* adr_urm;
};

nod *l[NMAX],*adresa;
long int n,m;
short int color[NMAX];

void citire();
void adauga(int,int);
void sortare_topologica();
void DF(int);
void push(int);
void scrie();

int main(){
  citire();
  sortare_topologica();
  scrie();
  fclose(f);
  fclose(g);
  return 0;
}

void citire(){
  fscanf(f,"%ld %ld",&n,&m);
  long int x,y;
  for(;m>0;m--){
    fscanf(f,"%ld %ld",&x,&y);
    adauga(x,y);
  }
}

void adauga(int i,int j){
  nod* p=new nod;
  p->vf=j;
  p->adr_urm=l[i];
  l[i]=p;
}

void sortare_topologica(){
  int i;
  for(i=1;i<=n;++i){
    if(color[i]==ALB)
      DF(i);
  }
}

void DF(int i){
  color[i]=GRI;
  nod* p=l[i];
  for(;p;p=p->adr_urm) 
    if(color[p->vf]==ALB)
      DF(p->vf);
  color[i]=NEGRU;
  push(i);
}

void push (int i){
  nod *p=new nod;
  p->vf=i;
  p->adr_urm=adresa;
  adresa=p;
}

void scrie(){
  for(nod* p=adresa;p;p=p->adr_urm)fprintf(g,"%d ",p->vf);
}