Cod sursa(job #2777703)

Utilizator cyg_dawidDavid Ghiberdic cyg_dawid Data 23 septembrie 2021 22:22:38
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <vector>

std::ifstream fin ("sortaret.in");
std::ofstream fout ("sortaret.out");

int const nmax = 50000;
bool done[nmax];
std::vector <std::vector<int>> adj;
std::vector <int> ans;
int n, m;

void solve (int x) {
    int cnt = adj[x].size();
    for (int i = 0; i < cnt; i++)
        if (!done[adj[x][i]]) {
            done[adj[x][i]] = true;
            solve (adj[x][i]);
        }
    ans.push_back(x);
}

int main () {
    fin >> n >> m;
    adj.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
    }
    for (int i = 1; i <= n; i++)
        if (!done[i]) {
            done[i] = true;
            solve(i);
        }
    for (int i = n - 1; i >= 0; i--)
        fout << ans[i] << " ";
    return 0;
}