Cod sursa(job #154187)

Utilizator maria_pparcalabescu maria daniela maria_p Data 10 martie 2008 23:00:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<cstdio>

const long MAX=50010;

struct point{
	long x;
	point *leg;
}*p,*lista[MAX];
long n,m,a[MAX],i,nr,x,y;
bool sel[MAX];

void dfs(long x){
	sel[x]=1;
	for(point *p=lista[x];p!=0;p=p->leg)
		if(sel[p->x]==0){
			dfs(p->x);
//			a[nr++]=p->x;
		}
	a[nr++] = x;

}

int main(){
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(;m>0;m--){
		scanf("%ld%ld",&x,&y);
		p=new point;
		p->x=y;
		p->leg=lista[x];
		lista[x]=p;
	}
	for(i=1;i<=n;i++)
		if(sel[i]==0) {
			dfs(i);
		}
	for(i=nr-1;i>=0;i--)
		printf("%ld ",a[i]);
	printf("\n");
	fclose(stdin);
	fclose(stdout);
	return 0;
}