Cod sursa(job #278522)

Utilizator alexandru92alexandru alexandru92 Data 12 martie 2009 13:04:43
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.32 kb
#include<stdio.h>
#define Nmax 50010
int n,v[Nmax],uz[Nmax],gre[Nmax],vf;
struct nod
     {
      int info;
      nod *urm;
     };
typedef nod *Lista;
Lista L[Nmax],U[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 DFS(int);
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);
       if(L[x])  Insert(L[x],U[x],y),U[x]=U[x]->urm;
         else Insert(L[x],NULL,y),U[x]=L[x];
       gre[y]++;
      }
   /*for(i=1;i<=n;++i)
      if(gre[i]==0)
         {if(L[n+1]) Insert(L[n+1],U[n+1],i),U[n+1]=U[n+1]->urm;
            else Insert(L[n+1],NULL,i),U[n+1]=L[n+1];
         uz[i]=1;}
   */
   for(i=1;i<=n;++i)
      if(!uz[i]) DFS(i);
   for(Lista p=L[n+1];p;p=p->urm) printf("%d ",p->info);
   return 0;
  }
void DFS(int x)
   {
    uz[x]=1;
    if(L[n+1]) Insert(L[n+1],U[n+1],x),U[n+1]=U[n+1]->urm;
      else Insert(L[n+1],NULL,x),U[n+1]=L[n+1];
    for(Lista p=L[x];p;p=p->urm)
       if(!uz[p->info]) DFS(p->info);
   /* if(L[n+1]) Insert(L[n+1],U[n+1],x),U[n+1]=U[n+1]->urm;
      else Insert(L[n+1],NULL,x),U[n+1]=L[n+1];
   */}