Cod sursa(job #286970)

Utilizator crissuMarin Cristina crissu Data 24 martie 2009 13:02:36
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.62 kb
#include<stdio.h>
int n, a[3500][3500], nrp[3500];
void citire();
void bfs();
int main(){
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	citire();
	bfs();
	return 0;
}
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, p=1, u=0, coada[3500];
	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);
			}
		}
	}
}