mfgnik

Untitled

Apr 10th, 2023
478
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.69 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <optional>
  4. #include <unordered_set>
  5. #include <vector>
  6.  
  7.  
  8. enum class Color {
  9.     WHITE = 0,
  10.     GREY = 1,
  11.     BLACK = 2,
  12. };
  13.  
  14. class Graph {
  15. public:
  16.     explicit Graph(int vertices_amount) : graph_(vertices_amount) {}
  17.  
  18.     void AddEdge(int from, int to) {
  19.         graph_[from].insert(to);
  20.         graph_[to].insert(from);
  21.     }
  22.  
  23.     const std::unordered_set<int>& GetVerticesList(int vertice) const {
  24.         return graph_[vertice];
  25.     }
  26.  
  27.     size_t GetVerticesAmount() const {
  28.         return graph_.size();
  29.     }
  30.  
  31. private:
  32.     std::vector<std::unordered_set<int>> graph_;
  33. };
  34.  
  35.  
  36. struct Visitor {
  37.     std::vector<Color> used;
  38.     std::vector<int> parent;
  39.     int cycle_start = -1;
  40.     int cycle_end = -1;
  41.  
  42.     Visitor(int vertices_amount) : used(vertices_amount, Color::WHITE), parent(vertices_amount, -1) {}
  43. };
  44.  
  45.  
  46. bool DFS(const Graph& graph, Visitor& visitor, int vertice, int par = -1) {
  47.     visitor.used[vertice] = Color::GREY;
  48.     for (int other_vertice: graph.GetVerticesList(vertice)) {
  49.         if (other_vertice == par) {
  50.             continue;
  51.         }
  52.         if (visitor.used[other_vertice] == Color::WHITE) {
  53.             visitor.parent[other_vertice] = vertice;
  54.             if (DFS(graph, visitor, other_vertice, vertice)) {
  55.                 return true;
  56.             }
  57.         }
  58.         else if (visitor.used[other_vertice] == Color::GREY) {
  59.             visitor.cycle_end = vertice;
  60.             visitor.cycle_start = other_vertice;
  61.             return true;
  62.         }
  63.     }
  64.     visitor.used[vertice] = Color::BLACK;
  65.     return false;
  66. }
  67.  
  68. int main() {
  69.     int vertices_amount;
  70.     std::cin >> vertices_amount;
  71.     Graph graph(vertices_amount);
  72.     for (int i = 0; i < vertices_amount; ++i) {
  73.         for (int j = 0; j < vertices_amount; ++j) {
  74.             int number;
  75.             std::cin >> number;
  76.             if (number == 1) {
  77.                 graph.AddEdge(i, j);
  78.             }
  79.         }
  80.     }
  81.     Visitor visitor(vertices_amount);
  82.     for (int i = 0; i < vertices_amount; ++i) {
  83.         if (DFS(graph, visitor, i)) {
  84.             std::cout << "YES\n";
  85.             std::vector<int> cycle;
  86.             for (int vertice = visitor.cycle_end; vertice != visitor.cycle_start; vertice = visitor.parent[vertice]) {
  87.                 cycle.push_back(vertice);
  88.             }
  89.             cycle.push_back(visitor.cycle_start);
  90.             std::reverse(cycle.begin(), cycle.end());
  91.             std::cout << cycle.size() << "\n";
  92.             for (auto vertice: cycle) {
  93.                 std::cout << vertice + 1 << " ";
  94.             }
  95.             return 0;
  96.         }
  97.     }
  98.     std::cout << "NO";
  99.     return 0;
  100. }
  101.  
Advertisement
Add Comment
Please, Sign In to add comment