Cod sursa(job #304575)

Utilizator TyberFMI Dogan Adrian Ioan Lucian Tyber Data 14 aprilie 2009 10:03:54
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include<stdio.h>
#define nmax 50001
struct tnod{
	int x;
	tnod*urm;
};
tnod *v[nmax],*ad;
void list(int);
void top();
void add(tnod*&,int);
void df(int);
int n,m,c[nmax];
int main(){
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(;m>=0;m--){
		int x,y;
		scanf("%d %d",&x,&y);
		add(v[x],y);
	}
	top();
	for(tnod*p=ad;p!=NULL;p=p->urm)
		printf("%d ",p->x);
	printf("\n");
	return 0;
}
void add(tnod*&d,int t){
	tnod*p;
	p=new tnod;
	p->x=t;
	p->urm=d;
	d=p;
}
void top(){
	for(int i=1;i<=n;i++)
		if(c[i]==0)
			df(i);
}
void df(int t){
	c[t]=1;
	for(tnod*p=v[t];p!=NULL;p=p->urm)
		if(c[p->x]==0)
			df(p->x);
	c[t]=2;
	list(t);
}
void list(int t){
	tnod*p;
	p=new tnod;
	p->x=t;
	p->urm=ad;
	ad=p;
}