Advertisement
Dzham

Untitled

Apr 15th, 2018
105
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.77 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <iterator>
  5. #include <unordered_map>
  6. #include <unordered_set>
  7. #include <string>
  8.  
  9. class Graph {
  10. private:
  11. int size_g;
  12. std::vector<std::vector<int>> data;
  13. std::vector<int> used;
  14.  
  15. public:
  16. std::vector<bool> isused;
  17. std::vector<int> colour;
  18. bool isisdouble = true;
  19. bool isiscycle = false;
  20. std::vector<int> cyclepath;
  21. std::unordered_map<int, int> parents;
  22.  
  23. Graph() {
  24. }
  25.  
  26. explicit Graph(int n) {
  27. data.resize(n);
  28. isused.resize(n);
  29. size_g = n;
  30. std::vector<int> c(n, 0);
  31. colour = c;
  32. }
  33.  
  34. void insert(int a, int b) {
  35. if (a != b) {
  36. data[a - 1].push_back(b);
  37. }
  38. }
  39.  
  40. void printgraph() {
  41. for (int i = 0; i < data.size(); i++) {
  42. for (auto j : data[i]) {
  43. std::cout << j << " ";
  44. }
  45. std::cout << '\n';
  46. }
  47. }
  48.  
  49. std::vector<int> dfs(int a) {
  50. std::vector<int> result;
  51. if (!isused[a - 1]) {
  52. isused[a - 1] = true;
  53. result.push_back(a);
  54. for (int i = 0; i < data[a - 1].size(); i++) {
  55. if (!isused[data[a - 1][i] - 1]) {
  56. std::vector<int> preres;
  57. preres = dfs(data[a - 1][i]);
  58. result.insert(result.end(), preres.begin(), preres.end());
  59. }
  60. }
  61. }
  62. return result;
  63. }
  64.  
  65. void colourdfs(int a, int c) {
  66. if (colour[a - 1] == 0 && isisdouble) {
  67. colour[a - 1] = c;
  68. for (int i = 0; i < data[a - 1].size(); i++) {
  69. if (colour[data[a - 1][i] - 1] == c) {
  70. isisdouble &= false;
  71. } else if (colour[data[a - 1][i] - 1] == 0) {
  72. colourdfs(data[a - 1][i], 3 - c);
  73. }
  74. }
  75. }
  76. }
  77.  
  78. bool isdouble() {
  79. for (int i = 0; i < size_g; i++) {
  80. colourdfs(i + 1, 1);
  81. }
  82. return isisdouble;
  83. }
  84.  
  85. void cycledfs(int a, int prev) {
  86. if (!isiscycle) {
  87. isused[a - 1] = true;
  88. parents[a] = prev;
  89. for (int i = 0; i < data[a - 1].size(); i++) {
  90. if (isused[data[a - 1][i] - 1] && data[a - 1][i] != prev && !isiscycle) {
  91. isiscycle = true;
  92. std::vector<int> v;
  93. int b = a;
  94. v.push_back(data[a - 1][i]);
  95. while (b != data[a - 1][i]) {
  96. v.push_back(b);
  97. b = parents[b];
  98. }
  99. cyclepath = v;
  100. } else if (!isused[data[a - 1][i] - 1]) {
  101. cycledfs(data[a - 1][i], a);
  102. }
  103. }
  104. }
  105. }
  106.  
  107. void iscycle() {
  108. for (int i = 0; i < size_g; i++) {
  109. if (!isused[i]) {
  110. std::vector<int> v;
  111. cycledfs(i + 1, -1);
  112. }
  113. }
  114. if (isiscycle) {
  115. std::cout << "YES\n";
  116. std::cout << cyclepath.size() << '\n';
  117. std::cout << cyclepath[0];
  118. for (int i = 1; i < cyclepath.size(); i++) {
  119. std::cout << " " << cyclepath[i];
  120. }
  121. } else {
  122. std::cout << "NO";
  123. }
  124. }
  125. };
  126.  
  127. int main() {
  128. int N, M;
  129. int a, b;
  130. std::cin >> N;
  131. if (N != 0) {
  132. Graph graph(N);
  133. for (int i = 0; i < N; i++) {
  134. for (int j = 0; j < N; j++) {
  135. std::cin >> a;
  136. if (a == 1) {
  137. graph.insert(i + 1, j + 1);
  138. }
  139. }
  140. }
  141. graph.iscycle();
  142. }
  143. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement