Cod sursa(job #2481256)

Utilizator davidegoldDavide Gold davidegold Data 26 octombrie 2019 17:52:14
Problema Sortare topologica Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.58 kb
#include <fstream>
#include <vector>
#include <unordered_set>


using namespace std;

const int VMAX = 50001;

ifstream cin("sortaret.in");
ofstream cout("sortaret.out");

// structure for representing the graph
//struct Node{
//    vector <Node*> next;
//    int num;
//    bool visited;
//};



void build_graph(const int &num_edges, vector<int> (&edges)[VMAX], vector<int> &in_deg) {
    for (int i = 0; i < num_edges; i++) {
        int u, v;
        cin >> u >> v;

        edges[u].push_back(v);
        in_deg[v] ++;
    }
}

void build_roots(const int &num_vertices, const vector<int> &in_deg, vector<int> &roots){
    for (int i = 1; i <= num_vertices; ++ i)
        if (in_deg[i] == 0)
            roots.push_back(i);
}

void dfs(int node, vector<int> (&edges)[VMAX],
         vector<int> &order, unordered_set <int> &visited) {

    visited.emplace(node);
    for (auto child : edges[node])
        if (visited.find(child) == visited.end())
            dfs(child, edges, order, visited);

    order.push_back(node);

}

void print_topological_order(vector<int> &order){
    for (int i = order.size()-1; i >= 0; --i)
        cout << order[i] << " ";
}


int main() {

    int num_vertices, num_edges;
    cin >> num_vertices >> num_edges;


    vector <int> edges[VMAX];
    vector <int> in_deg(num_vertices, 0);

    build_graph(num_edges, edges, in_deg);


    vector <int> roots;
    build_roots(num_vertices, in_deg, roots);

    vector <int> order;
    unordered_set <int> visited;

    for (int node : roots)
        dfs(node, edges, order, visited);

    print_topological_order(order);

    return 0;
}