Guest User

Untitled

a guest
Jan 19th, 2018
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.91 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #define MAXN 100000
  4.  
  5. int n, m, val, j;
  6. bool cycle = false;
  7. int clr[MAXN];
  8. std :: vector<int> g[MAXN];
  9. std :: vector <int> ans;
  10.  
  11. void dfs (int v)
  12. {
  13.     clr[v] = 1;
  14.     for (size_t i = 0; i < g[v].size(); ++i)
  15.     {
  16.         int to = g[v][i];
  17.         if (clr[to] == 0)
  18.             dfs(to);
  19.  
  20.         else if (clr[to] == 1)
  21.         {
  22.             cycle = true;
  23.             return;
  24.         }
  25.     }
  26.     ans.push_back(v);
  27.     clr[v] = 2;
  28. }
  29.  
  30. void topological_sort()
  31. {
  32.     ans.clear();
  33.     for (int i = 0; i < n; ++i)
  34.     {
  35.         if (clr[i] == 0)
  36.             dfs(i);
  37.     }
  38. }
  39.  
  40. int main()
  41. {  
  42.     std :: ifstream in ("topsort.in");
  43.     std :: ofstream out("topsort.out");
  44.  
  45.     in >> n >> m;
  46.     for (int i = 0; i < m; i++)
  47.     {
  48.         in >> j >> val;
  49.         g[j - 1].push_back(val - 1);
  50.     }
  51.  
  52.     topological_sort();
  53.     if (cycle == true)
  54.         out << "-1";
  55.     else
  56.         for (int i = ans.size() - 1; i >= 0; --i)
  57.         out << ans[i] + 1 << " ";
  58.  
  59.     in.close();
  60.     out.close();
  61.  
  62.     return 0;
  63. }
Add Comment
Please, Sign In to add comment