Cod sursa(job #3136539)

Utilizator DavidLDavid Lauran DavidL Data 6 iunie 2023 21:21:17
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

const int NMAX = 50005;

int n, m;
vector<int> G[NMAX], inv[NMAX];
bool active[NMAX], done[NMAX];
vector<int> order;

void read() {
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; fin >> u >> v;
        G[u].push_back(v);
        inv[v].push_back(u);
    }
}

void sth(int vertex) {
    active[vertex] = true;
    for (int v: inv[vertex])
        if (!done[v] && !active[v])
            sth(v);
    active[vertex] = false;
    done[vertex] = true;
    order.push_back(vertex);
}

int main() {
    read();
    for (int i = 1; i <= n; i++) 
        if (!done[i])
            sth(i);

    //cout << order.size();
    for (int x: order)
        fout << x << " ";

    return 0;
}