Cod sursa(job #2539990)

Utilizator cip_ionescuCiprian Ionescu cip_ionescu Data 6 februarie 2020 16:58:34
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <array>
#include <queue>
#include <stack>

#define MAX_N 50000
#define MAX_M 100000

using std::cin;
using std::cout;

template <typename T, typename C = T>
struct Node {
    T node;
    Node *next;
    C weight;
};

template <typename T, size_t N, size_t M>
class Graph {
public:
    size_t size;
    
    void add(const T& x, const T& y) {
        _nodes[++size].node = y;
        _nodes[size].next = _list[x];
        _list[x] = &_nodes[size];
    }
    
    void add_weighted(const T& x, const T& y, const T& weight) {
        _nodes[++size].node = y;
        _nodes[size].weight = weight;
        _nodes[size].next = _list[x];
        _list[x] = &_nodes[size];
    }
    
    Node<T>& get_node(const T& x) {
        return *_list[x];
    }
    
    bool visited(const T& x) {
        return _visited[x];
    }
    
    void visit(const T& x) {
        _visited[x] = true;
    }
    
    void reset() {
        for (auto &it : _visited) it = false;
    }
private:
    std::array<Node<T>, M> _nodes;
    std::array<Node<T>*, N> _list;
    
    std::array<bool, N> _visited;
};

std::stack<int> s;

template <typename T, size_t N, size_t M>
void top_sort(Graph<T, N, M>& g, const T& x) {
    g.visit(x);
    
    Node<T>* p = &g.get_node(x);
    
    while (p) {
        if (!g.visited(p->node))
            top_sort(g, p->node);
        p = p->next;
    }

    s.push(x);
}

Graph<int, 1 + MAX_N, 1 + MAX_M> g;

int main(int argc, char const *argv[])
{
    std::ifstream fin("sortaret.in");
    std::ofstream fout("sortaret.out");

    int n, m, x, y;

    fin >> n >> m;
    for (int i = 1 ; i <= m ; i++) {
        fin >> x >> y;
        g.add(x, y);
    }

    for (int i = 1 ; i <= n ; i++)
        if (!g.visited(i)) top_sort(g, i);
    
    while (!s.empty()) {
        fout << s.top() << ' ';
        s.pop();
    }
    return 0;
}