Cod sursa(job #2930538)

Utilizator matthriscuMatt . matthriscu Data 28 octombrie 2022 17:15:00
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include <bits/stdc++.h>
using namespace std;

vector<int> topsort(const vector<vector<int>>& adj) {
    vector<int> ans;
    vector<bool> visited(adj.size(), 0);

    function<void(int)> dfs = [&](int current) {
        visited[current] = 1;

        for (int neigh : adj[current])
            if (!visited[neigh])
                dfs(neigh);

        ans.push_back(current);
    };

    for (size_t i = 0; i < adj.size(); ++i)
        if (!visited[i])
            dfs(i);

    reverse(ans.begin(), ans.end());

    return ans;
}

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

    int n, m;
    fin >> n >> m;

    vector<vector<int>> adj(n);
    for (int i = 1, x, y; i <= m; ++i) {
        fin >> x >> y;
        adj[x - 1].push_back(y - 1);
    }

    for (int x : topsort(adj))
        fout << x + 1 << ' ';
    fout << '\n';
}