Advertisement
Guest User

Untitled

a guest
Aug 23rd, 2017
57
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.32 KB | None | 0 0
  1. #include "stdafx.h"
  2. #include <iostream>
  3. #include <vector>
  4. #include <set>
  5. #include <algorithm>
  6. #include <queue>
  7.  
  8. using namespace std;
  9.  
  10. vector <bool> used;
  11. vector <bool> colour;
  12. int time = 0;
  13. vector <int> tin;
  14. vector <int> tout;
  15. vector <int> ans;
  16.  
  17. void dfs(int v, vector <vector<int>> & a, bool col)
  18. {
  19. tin[v] = ++time;
  20. used[v] = true;
  21. colour[v] = !col;
  22. for (auto i = a[v].begin(); i != a[v].end(); i++)
  23. if (!used[*i])
  24. dfs(*i, a, !col);
  25. tout[v] = ++time;
  26. ans.push_back(v);
  27. }
  28.  
  29. int main()
  30. {
  31. #ifdef _DEBUG
  32. freopen("input.txt", "r", stdin);
  33. freopen("output.txt", "w", stdout);
  34. #endif
  35. int n;
  36. cin >> n;
  37.  
  38. vector <vector <int>> g(n, vector <int>(n));
  39. vector <vector <int>> a(n);
  40.  
  41. used.resize(n);
  42. colour.resize(n);
  43. tin.resize(n);
  44. tout.resize(n);
  45.  
  46. for (int i = 0; i < n; i++)
  47. for (int j = 0; j < n; j++)
  48. cin >> g[i][j];
  49.  
  50. for (int i = 0; i < n; i++)
  51. for (int j = 0; j < n; j++)
  52. {
  53. if (g[i][j] == 1)
  54. a[i].push_back(j);
  55. }
  56.  
  57. for (int i = 0; i < n; i++)
  58. if (!used[i])
  59. dfs(i, a, false);
  60.  
  61. /*
  62. for (int i = 0; i < n; i++)
  63. cout << tin[i] << ' ';
  64. cout << endl;
  65.  
  66. for (int i = 0; i < n; i++)
  67. cout << tout[i] << ' ';
  68. cout << endl;
  69. */
  70.  
  71. reverse(ans.begin(), ans.end());
  72. for (int i = 0; i < ans.size(); i++)
  73. cout << ans[i] + 1 << ' ';
  74.  
  75. return 0;
  76. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement