Cod sursa(job #1235548)

Utilizator crucerucalinCalin-Cristian Cruceru crucerucalin Data 29 septembrie 2014 23:00:03
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.23 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <stack>


void dfs(int node,
         std::vector< std::list<int> > &adj,
         std::vector<bool> &visited,
         std::stack<int> &result)
{
    visited[node] = true;

    for (auto &i : adj[node])
        if (!visited[i])
            dfs(i, adj, visited, result);

    result.push(node);
}

std::stack<int> sort_topo(std::vector< std::list<int> > &adj,
                          std::vector<bool> &visited)
{
    std::stack<int> result;

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

    return result;
}

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

    int N, M;
    in >> N >> M;

    std::vector< std::list<int> > adj(N);

    for (int i = 0; i < M; ++i) {
        int x, y;
        in >> x >> y;

        adj[x-1].push_front(y-1);
    }
    in.close();

    std::vector<bool> visited(N, false);
    std::stack<int> ordered = sort_topo(adj, visited);
    if (ordered.empty())
        return 1;

    while (!ordered.empty()) {
        int vertex = ordered.top();
        ordered.pop();

        out << vertex+1 << " ";
    }

    out.close();
    return 0;
}