Cod sursa(job #144685)

Utilizator gigi_becaliGigi Becali gigi_becali Data 27 februarie 2008 21:01:23
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.7 kb
#include <cstdio>
#include <cstdlib>
#define maxn 50001

struct nod {unsigned short x; nod *n;}__attribute__ ((packed));

int n;
int sol[maxn],ns;
bool use[maxn];
nod *a[maxn];

inline void dfs(unsigned short n)
{
    if(use[n])return ;
    use[n]=1;


    for(nod *i=a[n]; i ;i=i->n)
	if(!use[i->x])
	    dfs(i->x);
    sol[++ns]=n;
}

int main()
{
    freopen("sortaret.in","r",stdin);
    int m, p, q;
    nod *t;
    scanf("%d %d\n", &n,&m);
    while(m--)
    {
	scanf("%d %d\n", &p, &q);
	t=new nod;
	t->x=q;
	t->n=a[p];
	a[p]=t;
    }
    
    int i;
    for(i=1;i<=n;++i)
	if(!use[i]) dfs(i);

freopen("sortaret.out","w",stdout);
    for(i=n;i>=1;--i)printf("%d ", sol[i]);
    printf("\n");
    return 0;
}