Cod sursa(job #1413768)

Utilizator PureGPureGains PureG Data 2 aprilie 2015 08:21:09
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
/*
    Keep It Simple!
*/

#include <vector>
#include <fstream>

using namespace std;

const int kMaxN = 50005;

int N,M;
vector<int> G[kMaxN],topo;
bool used[kMaxN];

void TopoSort(int node) {
    used[node] = true;
    for (auto it:G[node])
        if(!used[it])
            TopoSort(it);
    topo.push_back(node);
}

void Solve() {
    ifstream fin("sortaret.in");
    fin >> N >> M;
    for (int i(1); i <= M; ++i) {
        int x,y;
        fin >> x >> y;
        G[x].push_back(y);
    }
    fin.close();
    for (int i(1); i<= N; ++i)
        if (!used[i])
            TopoSort(i);
    ofstream fout("sortaret.out");
    for (vector<int>::reverse_iterator it = topo.rbegin(); it!=topo.rend(); it++)
        fout << *it << ' ';
    fout << '\n';
    fout.close();
}

int main() {
    Solve();
    return 0;
}