Cod sursa(job #645052)

Utilizator valentin.harsanValentin Harsan valentin.harsan Data 8 decembrie 2011 10:33:41
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<fstream>
#include<vector>
using namespace std;

const int N=50010;

ifstream in("sortaret.in");
ofstream out("sortaret.out");

int n,m,ordine[N],nr,tm[N],nrt;
vector<int> g[N];
bool viz[N];

void df(int nod) {
    vector<int>::iterator it;

    viz[nod]=true;

    for(it=g[nod].begin();it!=g[nod].end();++it) if(!viz[*it])
        df(*it);

    tm[++nrt]=nod;

}

int main() {
    int i,a,b;

    in >> n >> m;

    for(i=1;i<=n;++i) {
        in >> a >> b;

        g[a].push_back(b);
    }

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

        while(nrt)
            ordine[++nr]=tm[nrt--];
    }

    for(i=1;i<=n;++i)
        out << ordine[i] << " ";

    return 0;
}