Cod sursa(job #2324580)

Utilizator igsifvevc avb igsi Data 21 ianuarie 2019 01:34:04
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <algorithm>
#include <fstream>
#include <iterator>
#include <vector>

void dfs(const int v,
         std::vector<bool> &visited,
         std::vector<int> &tsort,
         const std::vector<std::vector<int>> &adj)
{
    visited[v] = true;

    for (int u : adj[v])
        if (!visited[u])
            dfs(u, visited, tsort, adj);
    tsort.push_back(v + 1);
}

std::vector<int> get_tsort(const std::vector<std::vector<int>> &adj)
{
    const int n = adj.size();
    std::vector<bool> visited(n, false);
    std::vector<int> tsort;

    for (int v = 0; v < n; ++v)
        if (!visited[v])
            dfs(v, visited, tsort, adj);

    return tsort;
}

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

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

    int u, v;
    std::vector<std::vector<int>> adj(n, std::vector<int>());
    for (; m; m--)
    {
        fin >> u >> v;
        adj[u - 1].push_back(v - 1);
    }

    auto tsort = get_tsort(adj);

    std::reverse_copy(tsort.begin(), tsort.end(), std::ostream_iterator<int>(fout, " "));
    fout << '\n';

    return 0;
}