Cod sursa(job #2195547)

Utilizator horiahoria1Horia Alexandru Dragomir horiahoria1 Data 16 aprilie 2018 18:43:52
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <fstream>
#include <vector>

void dfs(int node, std::vector<bool> &visited, std::vector<int> *adj, std::vector<int> &result) {
    visited[node] = true;
    for (auto &neighbour : adj[node]) {
        if (!visited[neighbour]) {
            dfs(neighbour, visited, adj, result);
        }
    }
    result.push_back(node);
}

int main() {

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

    int n, m;
    in >> n >> m;

    int nr = 0;
    std::vector<int> adj[n + 1];
    std::vector<bool> visited(n + 1, false);

    int i;
    int u, v;

    for (i = 0; i < m; ++i) {
        in >> u >> v;
        adj[u].push_back(v);
    }

    std::vector<int> result;

    for (i = 1; i <= n; ++i) {
        if (!visited[i]) {
            dfs(i, visited, adj, result);
        }
    }

    for (i = n - 1; i >= 0; --i) {
        out << result[i] << ' ';
    }

    in.close();
    out.close();

    return 0;
}