Advertisement
Guest User

Untitled

a guest
Jan 19th, 2020
73
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.32 KB | None | 0 0
  1.  
  2. #define _GLIBCXX_DEBUG
  3. #include <iostream>
  4. #include <vector>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. vector<vector<int>> g;
  10. vector<int> col;
  11. vector<int> out_time;
  12.  
  13. int dfs(int u){
  14. int res = 0;
  15. col[u] = 2;
  16. for (int x : g[u])
  17. {
  18. if (col[x] == 2){
  19. return res = 1;
  20. }
  21. if (col[x] == 0){
  22. res = dfs(x);
  23. }
  24. }
  25. col[u] = 1;
  26. return res;
  27. }
  28.  
  29. void top_sort(int u){
  30. if (col[u]){
  31. return;
  32. }
  33. col[u] = 1;
  34. for (int x : g[u])
  35. {
  36. top_sort(x);
  37. }
  38. out_time.push_back(u);
  39. return;
  40. }
  41.  
  42. int main(){
  43. int v, e;
  44. cin >> v >> e;
  45. g.resize(v + 10);
  46. col.resize(v + 10);
  47. out_time.resize(v + 10);
  48. fill(col.begin(), col.end(), 0);
  49. for(int i = 0; i < e; i++){
  50. int a, b;
  51. cin >> a >> b;
  52. a--;
  53. b--;
  54. g[a].push_back(b);
  55. }
  56. for (int i = 0; i < v; i++){
  57. if (!col[i] && dfs(i))
  58. {
  59. cout << -1 << '\n';
  60. return 0;
  61. }
  62. }
  63. fill(col.begin(), col.end(), 0);
  64. for (int i = 0; i < v; i++){
  65. if (!col[i]){
  66. top_sort(i);
  67. }
  68. }
  69. reverse(out_time.begin(), out_time.end());
  70. for (int i = 0; i < v; i++){
  71. cout << out_time[i] + 1 << ' ';
  72. }
  73.  
  74. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement