Cod sursa(job #928083)

Utilizator StanAndreiAndrei Stan StanAndrei Data 26 martie 2013 11:17:05
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <stdio.h>
#include <list>

using namespace std;

list<int> G[100005],ST;
bool viz[100005];

int N,M;

void cit()
{
    scanf("%d %d\n",&N,&M);

    int a,b,i;
    for (i=1;i<=M;i++)
    {
        scanf("%d %d\n",&a,&b);
        G[a].push_back(b);
    }
}

void dfs(int p)
{
    viz[p]=1;
    ST.push_back(p);

    list<int>:: iterator it;

    for (it=G[p].begin();it!=G[p].end();++it)
        if (!viz[*it])
            dfs(*it);
}

void rez()
{
    int i;
    for (i=1;i<=N;i++)
        if (!viz[i])
            dfs(i);

    list<int>:: iterator it;
    it=ST.end();
    it--;
    for (it;it!=ST.begin();--it)
        printf("%d ",*it);
    it=ST.begin();
    printf("%d",*it);
    printf("\n");
}

int main()
{
    freopen ("sortaret.in","r",stdin);
    freopen ("sortaret.out","w",stdout);

    cit();
    rez();

    fclose(stdin);
    fclose(stdout);
    return 0;
}