Cod sursa(job #1005084)

Utilizator gabrieligabrieli gabrieli Data 4 octombrie 2013 05:12:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

void sortaret(
        const int x,
        const vector<vector<int>> &g,
        vector<bool> &v,
        stack<int> &sol)
{
    v[x] = true;
    for (auto y : g[x])
        if(!v[y])
            sortaret(y, g, v, sol);

    sol.push(x);
}

int main()
{
    ifstream fin("sortaret.in");
    ofstream fout("sortaret.out");

    int n, m;
    fin >> n >> m;
    vector<vector<int>> g(n+1, vector<int>());
    vector<bool> v(n+1, false);
    stack<int> sol;

    for (int x, y, i = 0; i < m; ++i){
        fin >> x >> y;
        g[x].push_back(y);
    }

    for (int x = 1; x <= n; ++x)
        if (!v[x])
            sortaret(x, g, v, sol);

    while (!sol.empty()) {
        fout << sol.top() << ' ';
        sol.pop();
    }
    fout << endl;

    return 0;
}