Cod sursa(job #252084)

Utilizator socheoSorodoc Ionut socheo Data 3 februarie 2009 21:26:14
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb

#include<stdio.h>

using namespace std;
int a[2][10000],st[50000],c[50000],o,i,j,n,m,k,deg[50000],q,s[50000];

int main(void){
freopen("sortaret.in","r",stdin);
freopen("sortaret.out","w",stdout);
   scanf("%d%d",&n,&m);
   k=1;
   for(o=1;o<=m;o++)
   { scanf("%d%d",&i,&j);
     a[0][k]=j;
     a[1][k]=st[i];
     st[i]=k;
     k++;
  deg[j]++;
   }
   k=0;
for(i=1;i<=n;i++)
 if(deg[i]==0)
	c[++k]=i;
for(i=1;i<=n;i++)
{ q=c[i];
  j=st[i];
   while(a[1][j]!=0)
   { deg[a[0][j]]--;
     if(deg[a[0][j]]==0)
       c[++k]=a[0][j];
	 j=a[1][j];
   }
  deg[a[0][j]]--;
 if(deg[a[0][j]]==0)
   c[++k]=a[0][j];	 
}
for(i=1;i<=n;i++)
		printf("%d ",c[i]);	 
return 0;
}