Cod sursa(job #278442)

Utilizator alexandru92alexandru alexandru92 Data 12 martie 2009 12:31:33
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.2 kb
#include<stdio.h>
#define Nmax 50010
int n,v[Nmax],uz[Nmax],vf;
struct nod
     {
      int info;
      nod *urm;
     };
typedef nod *Lista;
Lista L[Nmax];
inline void Insert(Lista &prim,Lista p,int x)
     {
      Lista q=new nod;
      q->info=x;
      if(prim){q->urm=p->urm; p->urm=q;}
        else {q->urm=prim; prim=q;}
      }
void add(Lista &prim,int x)
   {
    if(!prim) {Insert(prim,NULL,x);return;}
    Lista p;
    for(p=prim;p;p=p->urm)
       if(p->info==x) return;
    for(p=prim;p->urm&&p->urm->info<x;p=p->urm);
    Insert(prim,p,x);
   }
void sort();
int main()
  {int i,m,x,y;
   freopen("sortaret.in","rt",stdin);
   freopen("sortaret.out","wt",stdout);
   scanf("%d %d",&n,&m);
   for(i=1;i<=m;++i)
      {scanf("%d %d",&x,&y);
       add(L[x],y);
       }
   for(i=1;i<=n;++i)
      if(!uz[i])
        {vf=1; v[1]=i; uz[i]=1;
         sort();
         }
   return 0;
  }
void sort()
   {
    if(vf)
      {int x;
           x=v[vf--]; printf("%d ",x);
           for(Lista p=L[x];p;p=p->urm)
              if(!uz[p->info])
                {
                 v[++vf]=p->info; uz[p->info]=1;
                 sort();
                }
           }
   }