Cod sursa(job #286991)

Utilizator ab_ank_1Baciu Ancuta ab_ank_1 Data 24 martie 2009 13:28:39
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda placinta Marime 0.61 kb
#include<stdio.h>

short int a[2500][2500],n,nrp[2500];
void citire(){
	int m,x,y;
	scanf("%hd%hd",&n,&m);
	while(m--){
		scanf("%d%d",&x,&y);
		a[x][++a[x][0]]=y;
		++nrp[y];
	}
}
void bfs(){
	short int i, x,y,u=0,p=1,coada[2500];
	for(i=1;i<=n;++i)
		if(nrp[i]==0){
			coada[++u]=i;
			printf("%hd ", i);
		}
	while(p<=u){
		x=coada[p++];
		for(i=1;i<=a[x][0];++i){
			y=a[x][i];
			--nrp[y];
			if(nrp[y]==0){
				coada[++u]=y;
				printf("%hd ",y);
			}
		}
	}
}
int main(){
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	citire();
	bfs();
	return 0;
}