Cod sursa(job #502399)

Utilizator DuxarFII-Stefan-Negrus Duxar Data 19 noiembrie 2010 11:48:50
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.85 kb
#include<cstdio>
#define nmax 50002

using namespace std;


struct NodAR
{
	int inf;
	struct NodAR* next;
};

typedef NodAR* NAR;

NAR a[nmax];
int n,m,di[nmax];

void read();
void adaug(int,int);
void solve();

int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	
	read();
	solve();
	return 0;
}

void read()
{
	int i,x,y;
	scanf("%ld%ld",&n,&m);
	for (i=1;i<=m;++i)
	{
		scanf("%ld%ld",&x,&y);
		adaug(x,y);
		di[y]++;
	}
}

void adaug(int x,int y)
{
	NAR p=new NodAR;
	p->inf=y;
	p->next=a[x];
	a[x]=p;
}

void solve()
{
	int i,pi=0,u,Q[nmax],z;
	NAR p;
	for (i=1;i<=n;++i)
		if (!di[i])
			Q[++pi]=i;
	u=pi;
	pi=1;
	while (pi<=u)
	{
		z=Q[pi++];
		printf("%ld ",z);
		for (p=a[z];p;p=p->next)
		{
			di[p->inf]--;
			if (!di[p->inf]) Q[++u]=p->inf;
		}
	}
}