Cod sursa(job #278192)

Utilizator alexandru92alexandru alexandru92 Data 12 martie 2009 10:04:45
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.11 kb
#include<stdio.h>
#define Nmax 50001
struct nod
     {
      int info;
      nod *urm;
     };
typedef nod *Lista;
Lista L[Nmax],U[Nmax];
int v[Nmax];
bool uz[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->urm&&p->urm->info<x;p=p->urm);
    Insert(prim,p,x);
   }
void sort();
int main()
  {int n,m,i,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);
     }
   printf("1 "); v[1]=1; uz[1]=1;
   sort();
   return 0;
  }
int x,prim=1,ultim=1;
void sort()
   {Lista p;
    if(ultim>=prim)
      {x=v[prim++];
       for(p=L[x];p;p=p->urm)
          if(!uz[p->info])
             {printf("%d ",p->info);
              v[++ultim]=p->info; uz[p->info]=1;
              sort();
             }
       }
    }