Cod sursa(job #391650)

Utilizator vicenzo_cnuStan Alexandru Dan vicenzo_cnu Data 6 februarie 2010 00:12:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<stdio.h>
#define Nmax 50001
typedef struct nod{int vf;
                  nod *leg;} 
                  *pnod,nod;      
pnod L[Nmax];
pnod w;
int v[Nmax],n,m;

void add(int a,int b)
{pnod p=new nod;
p->vf=b;
p->leg=L[a];
L[a]=p;}

void citire()
{freopen("sortaret.in","r",stdin);
scanf("%d %d",&n,&m);
int a,b;
  while(m--)
    {scanf("%d %d",&a,&b);
      add(a,b);}
fclose(stdin);
}

void push(int nodt)
{pnod p=new nod;
p->vf=nodt;
p->leg=w;
w=p;
}

void Df(int nodt)
{v[nodt]=1;
pnod p=new nod;
p=L[nodt];
  while(p)
    {if(v[p->vf]==0)
      Df(p->vf);
      p=p->leg;}
  v[nodt]=2;
  push(nodt);
  }
void sort()
{int i;
  for(i=1;i<=n;++i)
    if(v[i]==0)
      Df(i);
}
void afisare()
{freopen("sortaret.out","w",stdout);
  while(w)
    {printf("%d ",w->vf);
      w=w->leg;}
fclose(stdout);
}

int main()
{citire();
sort();
afisare();
return 0;}