Advertisement
Guest User

Untitled

a guest
Apr 24th, 2018
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.17 KB | None | 0 0
  1. #include <fstream>
  2. #include <vector>
  3. #include <stack>
  4.  
  5.  
  6. using namespace std;
  7.  
  8. ifstream cin("topsort.in");
  9. ofstream cout("topsort.out");
  10.  
  11. vector<vector<int>> g;
  12. vector<int> Color, Numbers;
  13.  
  14. stack<int>Stack;
  15.  
  16. int node, edge, t1, t2;
  17.  
  18.  
  19. bool dfs(int v)
  20. {
  21. if (Color[v] == 1)
  22. return true;
  23. if (Color[v] == 2)
  24. return false;
  25. Color[v] = 1;
  26. for (int i = 0;i < g[v].size();i++)
  27. {
  28. if (dfs(g[v][i]))
  29. return true;
  30. }
  31. Stack.push(v);
  32. Color[v] = 2;
  33. return false;
  34. }
  35. bool topsort()
  36. {
  37. bool cycle;
  38. for (int i = 1;i <= node;i++)
  39. {
  40. cycle = dfs(i);
  41. if (cycle)
  42. return false;
  43. }
  44. for (int i = 1;i <= node;i++)
  45. {
  46. Numbers[i] = Stack.top();
  47. Stack.pop();
  48. }
  49. return false;
  50. }
  51. void create(const int node, const int edge)
  52. {
  53. g.resize(node + 1);
  54. for (int i = 0;i < edge;i++)
  55. {
  56. cin >> t1 >> t2;
  57. if (t1 != t2)
  58. {
  59. g[t1].push_back(t2);
  60. }
  61. }
  62. }
  63. int main()
  64. {
  65. cin >> node >> edge;
  66. Numbers.resize(node + 1);
  67. create(node, edge);
  68. for (int i = 0;i < node+1;i++)
  69. Color.push_back(0);
  70. topsort();
  71. if (Numbers[1] !=0)
  72. {
  73. for (int i = 1;i <= node;i++)
  74. cout << Numbers[i] << ' ';
  75. }
  76. else cout << -1;
  77.  
  78.  
  79. return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement