Cod sursa(job #522754)

Utilizator BlaugranasEnal Gemaledin Blaugranas Data 16 ianuarie 2011 00:39:23
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include<stdio.h>
#include<stdlib.h>
#define N 50001
#define M 100001
long n,i,j,k,m,c[N],*g[N],a[M],b[M],deg[N],v[N],t;

int contine(long g[N],long n,long x)
{for(i=0;i<n;i++)
if(g[i]==x)
       return 1;
return 0;}

void explorare(long *k,long i)
{c[i]=1;
for(j=0;j<deg[i];j++)
if(c[g[i][j]]==0)
      explorare(k,g[i][j]);
v[++(*k)]=i;}

int main()
{freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++)
       {c[i]=0;
       deg[i]=0;}
for(k=1;k<=m;k++)
       {scanf("%ld%ld",&a[k],&b[k]);
       deg[a[k]]++;}
for(i=1;i<=n;deg[i++]=0)
       g[i]=(long*)malloc((deg[i]+1)*sizeof(long));
for(k=1;k<=m;k++)
if(contine(g[a[k]],deg[a[k]],b[k])==0)
       g[a[k]][deg[a[k]]++]=b[k];
t=0;
for(i=1;i<=n;i++)
if(c[i]==0)
       explorare(&t,i);
for(j=1;j<=n;j++)
       printf("%ld ",v[j]);
fclose(stdin);
fclose(stdout);
return 0;}