Cod sursa(job #196367)

Utilizator blasterzMircea Dima blasterz Data 26 iunie 2008 08:39:33
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <cstdio>
#define N 50001
#define DIM 8192
struct nod { int x; nod *n;};

nod *a[N];
int n, m, st[N], nst;
bool use[N];

char ax[DIM+16];
int pz;

inline void cit(int &x)
{
    x=0;
    while(ax[pz]<'0' || ax[pz]>'9')
	if(++pz==DIM)fread(ax, 1, DIM, stdin), pz=0;

    while(ax[pz]>='0' && ax[pz]<='9')
    {
	x=x*10+ax[pz]-'0';
	if(++pz==DIM)fread(ax, 1, DIM, stdin), pz=0;
    }
}


inline void add(int i,int j)
{
    nod *p=new nod;
    p->x=j;
    p->n=a[i];
    a[i]=p;
}

void read()
{
    freopen("sortaret.in","r",stdin);

    cit(n);cit(m);
//    scanf("%d %d\n", &n, &m);
    int p, q;
    nod *t;
    while(m--)
    {
//	scanf("%d %d\n", &p,&q);
	cit(p);cit(q);
	add(p,q);
    }
}

inline void dfs(int n)
{
    use[n]=1;

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

int main()
{
    freopen("sortaret.out","w",stdout);
    read();
    int i;
    for(i=1;i<=n;++i) 
	if(!use[i]) dfs(i);
    
    for(i=n;i;--i)printf("%d ", st[i]);
    printf("\n");
    return 0;
}