Cod sursa(job #884640)

Utilizator paulbotabota paul paulbota Data 21 februarie 2013 09:40:43
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <cstdio>
#define MAXN 50002
#define FOR(i,a,b) for(i=a;i<=b;i++)

using namespace std;

struct graf
{
    int nod;
    graf *next;
};

graf *a[MAXN],*sol;
int n,m;
bool marked[MAXN];


inline void add_A(int x,int y)
{
    graf *q=new graf;
    q->nod=y;
    q->next=a[x];
    a[x]=q;
}

inline void add_S(int y)
{
    graf *q=new graf;
    q->nod=y;
    q->next=sol;
    sol=q;
}
inline void read()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    int i;
    scanf("%d %d",&n,&m);
    FOR(i,1,m)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        add_A(x,y);
    }
}

void dfs(int i)
{
    marked[i]=true;
    graf *q=a[i];
    for(;q;q=q->next)
        if(marked[q->nod]==false)
            dfs(q->nod);
    add_S(i);
}

int main()
{
    read();
    int i;
    FOR(i,1,n)
        if(marked[i]==false)
            dfs(i);
    graf *q=new graf;
    for(q=sol;q!=NULL;q=q->next)
        printf("%d ",q->nod);
    printf("\n");
    return 0;
}