Cod sursa(job #278482)

Utilizator cotofanaCotofana Cristian cotofana Data 12 martie 2009 12:44:55
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.69 kb
#include <stdio.h>
#define dim 50100

struct nod
{
	int nr;
	nod *urm;
};
int n, m, fol[dim];
nod *prim[dim], *list;

void add(nod *&p, int nr)
{
	nod *n1=new nod;
	n1->nr=nr;
	n1->urm=p;
	p=n1;
}

void dfs(int x)
{
	nod *p=prim[x];
	fol[x]=1;
	while (p)
	{
		if (fol[p->nr]==0) dfs(p->nr);
		p=p->urm;
	}
	add(list, x);
}

int main()
{
	int i, a, b;
	freopen("sortaret.in", "r", stdin);
	freopen("sortaret.out", "w", stdout);
	scanf("%d %d\n", &n, &m);
	for (i=1; i<=m; i++)
	{
		scanf("%d %d\n", &a, &b);
		add(prim[a], b);
	}
	for (i=1; i<=n; i++)
		if (fol[i]==0) dfs(i);
	while (list)
	{
		printf("%d ", list->nr);
		list=list->urm;
	}
	return 0;
}