Cod sursa(job #2223632)

Utilizator a_h1926Heidelbacher Andrei a_h1926 Data 20 iulie 2018 21:15:26
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
#include <fstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

typedef vector<vector<int>> Graph;

const string IN_FILE = "sortaret.in";
const string OUT_FILE = "sortaret.out";

void dfs(
        const Graph& graph,
        const int u,
        vector<bool>& visited,
        vector<int>& order) {
    visited[u] = true;
    for (const auto& v : graph[u]) {
        if (!visited[v]) {
            dfs(graph, v, visited, order);
        }
    }
    order.push_back(u);
}

vector<int> getTopologicalOrder(const Graph& graph) {
    auto visited = vector<bool>(int(graph.size()));
    auto order = vector<int>();
    for (int u = 0; u < int(graph.size()); u++) {
        if (!visited[u]) {
            dfs(graph, u, visited, order);
        }
    }
    reverse(order.begin(), order.end());
    return order;
}

Graph readGraph() {
    ifstream in(IN_FILE);
    int V, E;
    in >> V >> E;
    auto graph = Graph(V);
    for (int i = 0; i < E; i++) {
        int u, v;
        in >> u >> v;
        graph[u - 1].push_back(v - 1);
    }
    in.close();
    return graph;
}

void writeOutput(const vector<int>& order) {
    ofstream out(OUT_FILE);
    for (int i = 0; i < int(order.size()); i++) {
        out << order[i] + 1 << (i + 1 < int(order.size()) ? " " : "\n");
    }
    out.close();
}

int main() {
    const auto graph = readGraph();
    const auto order = getTopologicalOrder(graph);
    writeOutput(order);
    return 0;
}