Cod sursa(job #286987)

Utilizator ab_ank_1Baciu Ancuta ab_ank_1 Data 24 martie 2009 13:25:43
Problema Sortare topologica Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.59 kb
#include<stdio.h>

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