Cod sursa(job #255868)

Utilizator andyciupCiupan Andrei andyciup Data 10 februarie 2009 20:11:59
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include<stdio.h>
#define N 51000
int a, b, plus[N]={0}, minus[N]={0}, *succ[N],m,n;
void citesc_si_aloc()
{
	scanf("%d", &n);
	scanf("%d", &m);
	while(m--){
		scanf("%d", &a);
		scanf("%d", &b);
		plus[a]++;
		minus[b]++;
	}
	fclose(stdin);
	
	for(int i=1; i<=n;++i){
		succ[i]=new int[1+plus[i]];
		succ[i][0]=0;
	}
}

void citesc(){
	freopen("sortaret.in", "r", stdin);
	scanf("%d", &n);
	scanf("%d", &m);
	while(m--){
		scanf("%d", &a);
		scanf("%d", &b);
		succ[a][++succ[a][0]]=b;
	}
}

void bfs(){
	int left=0, right=0,coada[N], x;
	for(int i=1; i<=n;++i){
		if(minus[i]==0){
			coada[right++]=i;
			printf("%d ",i);
		}
	while(left!=right){
		x=coada[left++];
		for(int i=1;i<=plus[x];++i)
		{
			int y=succ
			[x][i];
			--minus[y];
			if(minus[y]==0)
			{
				coada[++right]=y;
				printf("%d ",y); 
			}
		}
	}
	}
}
	


int main(){
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	citesc_si_aloc();
	citesc();
	bfs();
	return 0;
}