Cod sursa(job #457726)

Utilizator S7012MYPetru Trimbitas S7012MY Data 21 mai 2010 11:30:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb
#include <cstdio>
#include <deque>
using namespace std;

struct nod {
	int x;
	nod *urm;
} *v[50001];

int n,m,viz[50001];
deque <int> lista;

void adaugare(int x,int y) {
	nod *p;
	p=new nod;
	p->x=y;
	p->urm=v[x];
	v[x]=p;
}

void dfs(int z) {
	nod *p;
	viz[z]=1;
	for(p=v[z]; p!=NULL;  p=p->urm)
		if(!viz[p->x])
			dfs(p->x);
	lista.push_front(z);

}

void st() {
	int i;
	for(i=1; i<=n; i++)
		if(!viz[i])
			dfs(i);
}

int main()
{
	int i,x,y;
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	scanf("%d %d",&n,&m);
	for(i=0; i<m; i++) {
		scanf("%d %d",&x,&y);
		adaugare(x,y);
	}
	st();
	deque<int>::iterator it;
	for(it=lista.begin(); it!=lista.end(); it++)
		printf("%d ",*it);
	return 0;
}