Advertisement
den4ik2003

Untitled

Apr 2nd, 2022
172
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.33 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using std::vector;
  5.  
  6. void DFS(int v, int p, vector<vector<int>>& neighbours, vector<std::string>& colour, vector<int>& parent, bool& flag) {
  7.   parent[v] = p;
  8.   colour[v] = "GREY";
  9.   for (int to : neighbours[v]) {
  10.     if (flag) {
  11.       break;
  12.     }
  13.     if (colour[to] == "BLACK") {
  14.       continue;
  15.     }
  16.     if (colour[to] == "GREY") {
  17.       std::cout << "YES\n";
  18.       flag = true;
  19.       vector<int> cycle;
  20.       int u = v;
  21.       while (u != to) {
  22.         cycle.push_back(u + 1);
  23.         u = parent[u];
  24.       }
  25.       cycle.push_back(to + 1);
  26.       for (int i = cycle.size() - 1; i >= 0; --i) {
  27.         std::cout << cycle[i] << " ";
  28.       }
  29.       colour[v] = "BLACK";
  30.       return;
  31.     }
  32.     DFS(to, v, neighbours, colour, parent, flag);
  33.   }
  34.   colour[v] = "BLACK";
  35. }
  36.  
  37. int main() {
  38.   int n, m;
  39.   std::cin >> n >> m;
  40.   vector<vector<int>> neighbours(n);
  41.   vector<std::string> colour(n, "WHITE");
  42.   vector<int> parent(n);
  43.   for (int j = 0; j < m; ++j) {
  44.     int l, r;
  45.     std::cin >> l >> r;
  46.     neighbours[l - 1].push_back(r - 1);
  47.   }
  48.   bool flag = false;
  49.   for (int i = 0; i < n; ++i) {
  50.     if (colour[i] == "WHITE") {
  51.       DFS(i, -1, neighbours, colour, parent, flag);
  52.       if (flag) {
  53.         break;
  54.       }
  55.     }
  56.   }
  57.   if (!flag) {
  58.     std::cout << "NO";
  59.   }
  60. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement