Cod sursa(job #170230)

Utilizator swift90Ionut Bogdanescu swift90 Data 2 aprilie 2008 16:04:06
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include<stdio.h>
#define maxn 50010
struct muchie{
	int x,y;
}muc[2*maxn];
int nod[maxn],sol[maxn],s,n,m;
int *nr[maxn];
void df(int i){
	int j;
	nod[i]=1;
	for(j=1;j<=nr[i][0];++j){
		if(!nod[nr[i][j]])
			df(nr[i][j]);
	}
	sol[++s]=i;
}
int main(){
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	int i;
	scanf("%d%d",&n,&m);
	for(i=0;i<m;++i){
		scanf("%d%d",&muc[i].x,&muc[i].y);
		++nod[muc[i].x];
	}
	for(i=1;i<=n;++i){
		nr[i]=new int [nod[i]+1];
		nr[i][0]=0;
		nod[i]=0;
	}
	for(i=0;i<m;++i)
		nr[muc[i].x][++nr[muc[i].x][0]]=muc[i].y;
	
	for(i=1;i<=n;++i){
		if(!nod[i])
			df(i);
	}
	
	for(i=n;i;--i)
		printf("%d ",sol[i]);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}