Cod sursa(job #798792)

Utilizator paul_gabryelPaul Buda paul_gabryel Data 17 octombrie 2012 12:14:59
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.76 kb

#include <cstdio>
#include <fstream>
#include <vector>

using namespace std;

#define pb push_back

vector<int> G[50001],sol;
int n,m;
bool v[50001];

void read ()
{
    ifstream in ("sortaret.in");
    in>>n>>m;
    for(int i,j;m;--m)
    {
        in>>i>>j;
        G[i].pb(j);
    }
}

void DFS (int nd)
{
    v[nd]=1;
    for(vector<int>::iterator it=G[nd].begin();it<G[nd].end();++it)
        if(!v[*it])
            DFS(*it);
    sol.pb(nd);
}

void out ()
{
    freopen ("sortaret.out","w",stdout);
    for(vector<int>::iterator it=sol.end()-1;it>=sol.begin();--it)
        printf("%d ",*it);
}

int main ()
{
    read ();
    for(int i=1;i<=n;++i)
        if(!v[i])
            DFS(i);
    out ();
    return 0;
}