Cod sursa(job #324898)

Utilizator ciprianfFarcasanu Alexandru Ciprian ciprianf Data 17 iunie 2009 20:31:18
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <stdio.h>
#include <stdlib.h>
#define N 50010
int n,m,*a[N],viz[N],v[N],sol[N];
void df(int x){
	viz[x]=1;
	printf("%d ",x);
	for(int i=1;i<=a[x][0];i++)
		if(viz[a[x][i]]==0) df(a[x][i]);
}
void solve(){
	int i,j,x;
	for(i=1;i<=n;i++)
		if(v[i]==0) sol[++sol[0]]=i;
	for(i=1;i<=sol[0];i++){
		x=sol[i];
		for(j=1;j<=a[x][0];j++){
			v[a[x][j]]--;
			if(v[a[x][j]]==0) sol[++sol[0]]=a[x][j];
		}
	}
	for(i=1;i<=n;i++)
		printf("%d ",sol[i]);
	printf("\n");
}
int main(){
	int i,x,y;
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++){
		a[i]=(int*)malloc(4);
		a[i][0]=0;
	}
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		a[x][0]++;//a[y][0]++;
		a[x]=(int*)realloc(a[x],(a[x][0]+3)*4);
		//a[y]=(int*)realloc(a[y],(a[y][0]+1)*4);
		a[x][a[x][0]]=y;//a[y][a[y][0]]=x;
		v[y]++;
	}
	solve();
	return 0;
}