Cod sursa(job #251913)

Utilizator socheoSorodoc Ionut socheo Data 3 februarie 2009 16:51:47
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;

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;
	 q=st[i];
     deg[a[0][q]]--;
     if(deg[a[0][q]]==0&&q<i)
		c[++k]=a[0][q]; 
	 do{ q=a[1][q];
		 deg[a[0][q]]--;
	     if(deg[a[0][q]]==0&&q<i)
			 c[++k]=a[0][q]; 
	        }while(a[1][q]!=0);	
	}	
for(i=1;i<=n;i++)
		printf("%d ",c[i]);	 
printf("\n");
return 0;
}