fork download 
  1. #include <unordered_map>
  2. #include <vector>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <functional>
  6. #include <stack>
  7. #include <cassert>
  8.  
  9. using namespace std;
  10.  
  11. void dfs(const unordered_multimap<int, int>& graph, vector<int>& color, int node, const function<void(int)> post_order_func)
  12. {
  13.   stack<int> nodes;
  14.   nodes.push(node);
  15.  
  16.   while (!nodes.empty())
  17.   {
  18.     int from = nodes.top();
  19.  
  20.     if (color[from] == 1)
  21.     {
  22.       color[from] = 2;
  23.       post_order_func(from);
  24.       nodes.pop();
  25.       continue;
  26.     }
  27.     else if (color[from] == 2)
  28.     {
  29.       nodes.pop();
  30.       continue;
  31.     }
  32.  
  33.     color[from] = 1;
  34.     auto range = graph.equal_range(from);
  35.  
  36.     for (auto it = range.first; it != range.second; ++it)
  37.     {
  38.       const auto& to = it->second;
  39.       if (color[to] == 0)
  40.       {
  41.         nodes.push(to);
  42.       }
  43.       else if (color[to] == 1)
  44.       {
  45.         throw runtime_error("Graph has cycle. Topological sort impossible.");
  46.       }
  47.     }
  48.   }
  49. }
  50.  
  51. void topological_sort(int n, const unordered_multimap<int, int>& graph, vector<int>& result)
  52. {
  53.   result.resize(n);
  54.   vector<int> color(n, 0);
  55.   int j = 0;
  56.   auto post_order_func = [&result, &j](int node) {
  57.     result[j++] = node;
  58.   };
  59.  
  60.   for (int i = 0; i < n; ++i)
  61.   {
  62.     if (color[i] == 0)
  63.     {
  64.       dfs(graph, color, i, post_order_func);
  65.     }
  66.   }
  67.  
  68.   reverse(begin(result), end(result));
  69. }
  70.  
  71. int main()
  72. {
  73.   int n, m;
  74.  
  75.   cin >> n >> m;
  76.  
  77.   unordered_multimap<int, int> graph;
  78.   vector<int> result(n, -1);
  79.  
  80.   for (int i = 0; i < m; ++i)
  81.   {
  82.     int from, to;
  83.     cin >> from >> to;
  84.     --from;
  85.     --to;
  86.     graph.emplace(from, to);
  87.   }
  88.  
  89.   try
  90.   {
  91.     topological_sort(n, graph, result);
  92.   }
  93.   catch (...)
  94.   {
  95.     cout << -1 << endl;
  96.     return 0;
  97.   }
  98.  
  99.   for (int i = 0; i < result.size(); ++i)
  100.   {
  101.     cout << result[i] + 1 << (i + 1 == result.size() ? '\n' : ' ');
  102.   }
  103. }
Success #stdin #stdout 0.01s 5472KB
comments (?)
stdin 
6 6
1 2
3 2
4 2
2 5
6 5
4 6
stdout 
4 6 3 1 2 5
https://ideone.com/0oMb91
language:
C++14 (gcc 8.3)
created:
1 year ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!