Cod sursa(job #286958)

Utilizator ovy2906Popescu Ovidiu ovy2906 Data 24 martie 2009 12:56:08
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.66 kb
#include<stdio.h>
const int N=50002, M=100002;
struct muchie{ int s,d; } m[M];
int *v[N];
int nr[N];
char u[N];
int l[N],p;

void df(int x)
{
	u[x]=1;
	for(int i=1;i<=nr[x];++i)
		if(!u[v[x][i]]) df(v[x][i]);
	l[++p]=x;
}
int main()
{
	freopen("sortaret.in","r",stdin);
	freopen("sortaret.out","w",stdout);
	int n,muchii,i;
	scanf("%d%d",&n,&muchii);
	for(i=0;i<muchii;++i)
	{
		scanf("%d%d",&m[i].s,&m[i].d);
		++nr[m[i].s];
	}
	for(i=1;i<=n;++i)
	{
		v[i]=new int[nr[i]+1];
		v[i][0]=0;
	}
	for(i=0;i<muchii;++i)
		v[m[i].s][++v[m[i].s][0]]=m[i].d;
	for(i=1;i<=n;++i)
		if(!u[i]) df(i);
	for(i=n;i;--i) 
		printf("%d ",l[i]);
	return 0;
}