Cod sursa(job #1976872)

Utilizator taigi100Cazacu Robert taigi100 Data 4 mai 2017 14:00:33
Problema Sortare topologica Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 0.82 kb
/*
    Keep It Simple!
*/

#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int MAX_N = 50000;

int N, M;
int viz[MAX_N];
vector<int> G[MAX_N];
stack<int> Sol;

void ReadInput() {
    ifstream f("sortaret.in");

    f >> N >> M;
    int x, y;
    for (int i = 1; i <= M; ++i) {
        f >> x >> y;
        G[x].push_back(y);
    }
}

void DFS(int node) {
    viz[node] = 1;
    for (auto son : G[node])
        if (!viz[son])
            DFS(son);
    Sol.push(node);
}

void Solve() {
    ReadInput();

    for (int i = 1; i <= N; ++i)
        if (!viz[i])
            DFS(i);

    ofstream g("sortaret.out");
    while (Sol.size()) {
        g << Sol.top() << " ";
        Sol.pop();
    }
    g << '\n';
}

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