Cod sursa(job #626903)

Utilizator d.andreiDiaconeasa Andrei d.andrei Data 28 octombrie 2011 16:17:35
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <cstdio>
#include <cstring>

#define file_in "sortaret.in"
#define file_out "sortaret.out"

#define nmax 101000

typedef struct nod{
	
	int val;
	nod * urm;
} * Qnod;

Qnod G[nmax];
int viz[nmax];
int sol[nmax];
int ord[nmax];
int N,M,a,b,i;

void add(Qnod & p, int x){
	
	Qnod c=new nod;
	
	c->val=x;
	c->urm=p;
	p=c;
}


void dfs(int nod){
	
	Qnod p;
	

	if (viz[nod])
		 return ;
	
	viz[nod]=1;
	
	for (p=G[nod];p!=NULL;p=p->urm)
		 if (!viz[p->val])
			  dfs(p->val);
		 	ord[++ord[0]]=nod;
}


int main(){
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);;
	
	scanf("%d %d", &N, &M);
	for (i=1;i<=M;++i){
		 
		 scanf("%d %d", &a, &b);
		 add(G[a],b);
	}
	
	for (i=1;i<=N;++i)
		 if (!viz[i])
			  dfs(i);
		 
	//memset(viz,0,sizeof(viz));

	
    for (i=ord[0];i>=1;--i)
           printf("%d ", ord[i]);

	return 0;
	
}