Cod sursa(job #412792)

Utilizator cosgbCosmin cosgb Data 5 martie 2010 23:47:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
# include <stdio.h>
long n,m,i,a,b,j;
int viz[50005];
long sol[50005];
struct nod 
{ nod * urm;
 long info;
};
nod * top[100005];

void read()
{ nod *p;
	for (i=1;i<=m;i++)
	{scanf ("%ld %ld",&a,&b);
     p=new nod;
	 p->info=b;
	 p->urm=top[a];
	 top[a]=p;
	}
}

void dfs(long i)
{ nod *p;
  viz[i]=1;
  if (top[i]==NULL)
           {sol[++j]=i;
            return;
		   }			
  p=top[i];
 
  while (p)
  { if (viz[p->info]==0)
     {viz[p->info]=1;
      dfs(p->info);
	 }
    if (p->urm==NULL) {sol[++j]=i;
	                   p=p->urm;
	                  }
	  else p=p->urm;
	 }
}

int main()
{ freopen ("sortaret.in","r",stdin);
  freopen ("sortaret.out","w",stdout);
  scanf ("%ld %ld",&n,&m);
  read();
  j=0;
  for (i=1;i<=n;i++)
  {if (viz[i]==0)
   dfs(i);
  }
  for (i=n;i>=1;i--)
	  {printf ("%ld ",sol[i]);}

  return 0;
}