Cod sursa(job #1137834)

Utilizator cosmin.pascaruPascaru Cosmin cosmin.pascaru Data 9 martie 2014 14:08:51
Problema Sortare topologica Scor 50
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <cstdio>
#include <vector>

using namespace std;

void DF(int x);

int n,m;
vector <int> v[50005];
vector <int> s;
bool viz[50005];

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

    scanf("%d %d",&n,&m);
    s.reserve(n);
    for (int i=1;i<=n;++i)
    {
        v[i].reserve(30000);
    }
    int x,y;
    for (int i=1;i<=m;++i)
    {
        scanf("%d %d",&x,&y);
        v[x].push_back(y);
    }

    for (int i=1;i<=n;++i)
    {
        if (!viz[i]) DF(i);
    }

    for (int i=s.size()-1;i>=0;--i)
        printf("%d ",s[i]);
    printf("\n");
    return 0;
}

void DF(int x)
{
    viz[x]=true;
    for (int i=0;i<v[x].size();++i)
        if (!viz[v[x][i]]) DF(v[x][i]);
    s.push_back(x);
}