Advertisement
Art_Uspen

Untitled

Apr 11th, 2021
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4.  
  5. class Graph {
  6. private:
  7. size_t n_vertexes;
  8. size_t n_edges;
  9. std::vector<std::vector<size_t>> m_adj_;
  10. std::vector<std::vector<size_t>> matrix_adj_;
  11. std::vector<bool> visited;
  12. // std::vector<size_t> conn_vert;
  13. std::vector<size_t> vert_colors;
  14. bool is_dic;
  15. bool is_cyc;
  16. bool cycle_finish;
  17. size_t vert_v;
  18.  
  19. public:
  20. std::vector<size_t> cycle_vertexes;
  21.  
  22. Graph(size_t N, size_t M, std::vector<std::vector<size_t>> m_adj) : n_vertexes(N), n_edges(M),
  23. m_adj_(std::move(m_adj)), visited(n_vertexes,
  24. false) {
  25. vert_colors.resize(n_vertexes + 1);
  26. is_dic = true;
  27. vert_v = 1000;
  28. }
  29.  
  30. Graph(size_t N, std::vector<std::vector<size_t>> matrix_adj) : n_vertexes(N), matrix_adj_(std::move(matrix_adj)),
  31. visited(n_vertexes,
  32. false) {
  33. vert_colors.resize(n_vertexes);
  34. is_cyc = false;
  35. cycle_finish = false;
  36. vert_v = 10000000;
  37. }
  38.  
  39. void dfs(size_t now = 1) {
  40. visited[now] = true;
  41. for (auto neig : m_adj_[now]) {
  42. if (!visited[neig]) {
  43. dfs(neig);
  44. }
  45. }
  46. }
  47.  
  48. void bipartite_one_comp(size_t vert = 1, size_t color = 1) {
  49. vert_colors[vert] = color;
  50. visited[vert] = true;
  51. for (auto neig : m_adj_[vert]) {
  52. if (vert_colors[neig] == vert_colors[vert]) {
  53. is_dic = false;
  54. return;
  55. } else if (vert_colors[neig] == 0) {
  56. bipartite_one_comp(neig, 3 - vert_colors[vert]);
  57. }
  58. }
  59. }
  60.  
  61. bool bipartite_all_comp() {
  62. for (size_t now = 1; now <= n_vertexes; ++now) {
  63. if (!visited[now]) {
  64. bipartite_one_comp(now);
  65. if (!is_dic) {
  66. return false;
  67. }
  68. }
  69. }
  70. return true;
  71. }
  72.  
  73. void cycle_one(size_t vert = 0, size_t ancestor = 100000000) {
  74. vert_colors[vert] = 1;
  75. visited[vert] = true;
  76. for (size_t neig = 0; neig < matrix_adj_[vert].size(); ++neig) {
  77. if (cycle_finish){
  78. return;
  79. }
  80. if (matrix_adj_[vert][neig] == 1) {
  81. if (vert_colors[neig] == 1 && neig != ancestor) {
  82. vert_v = neig;
  83. is_cyc = true;
  84. break;
  85. } else if (vert_colors[neig] == 0) {
  86. cycle_one(neig, vert);
  87. }
  88. }
  89. }
  90. vert_colors[vert] = 2;
  91. if (is_cyc && !cycle_finish) {
  92. if (vert != vert_v) {
  93. cycle_vertexes.push_back(vert);
  94. } else if (vert == vert_v) {
  95. cycle_vertexes.push_back(vert);
  96. cycle_finish = true;
  97. }
  98. }
  99. }
  100.  
  101.  
  102. bool cycle_all() {
  103. for (size_t now = 0; now < n_vertexes; ++now) {
  104. if (!visited[now]) {
  105. cycle_one(now);
  106. if (is_cyc) {
  107. return true;
  108. }
  109. }
  110. }
  111. return false;
  112. }
  113.  
  114. };
  115.  
  116. void
  117. dfs(size_t now, std::vector<std::vector<size_t>> &m_adj, std::vector<bool> &first_vis,
  118. std::vector<size_t> &conn_vert) {
  119. first_vis[now] = true;
  120. conn_vert.push_back(now);
  121. for (auto neig : m_adj[now]) {
  122. if (!first_vis[neig]) {
  123. dfs(neig, m_adj, first_vis, conn_vert);
  124. }
  125. }
  126. }
  127.  
  128. int main() {
  129. size_t N;
  130. std::cin >> N;
  131. std::vector<std::vector<size_t>> matrix_adj(N, std::vector<size_t>(N));
  132. size_t vert = 0;
  133. for (size_t i = 0; i < N; ++i) {
  134. for (size_t j = 0; j < N; ++j) {
  135. std::cin >> vert;
  136. matrix_adj[i][j] = vert;
  137. }
  138. }
  139. Graph g(N, matrix_adj);
  140. g.cycle_all();
  141. if (!g.cycle_vertexes.empty()) {
  142. std::cout << "YES\n";
  143. std::cout << g.cycle_vertexes.size() << "\n";
  144. for (unsigned long cycle_vertexe : g.cycle_vertexes) {
  145. std::cout << cycle_vertexe + 1 << " ";
  146. }
  147. } else {
  148. std::cout << "NO";
  149. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement