Ser1ousSAM

cycle

Oct 24th, 2020 (edited)
113
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. bool is_cycle = 0;
  5. vector <int> temp_s, ans;
  6. int st(int &start) {
  7.     int l=0, r = temp_s.size()-1, i;
  8.     while (l < r) {
  9.         i = (l + r) / 2;
  10.         if (temp_s[i] == start) {
  11.             return i;
  12.         }
  13.         else if (temp_s[i] > start) {
  14.             r = i;
  15.         }
  16.         else {
  17.             l = r;
  18.         }
  19.     }
  20.     return -1;
  21. }
  22. void push_ans(int start) {
  23.     start = st(start);
  24.     for (int i = start; i < temp_s.size(); i++) {//пушбэкаем ответ до серой вершины
  25.         ans.push_back(temp_s[i] + 1);
  26.     }
  27. }
  28. void dfs(int v, vector <int>& visited, vector<vector<int>>& graph) {
  29.     visited[v] = 1; // отмечаем, что вошли в вершину
  30.     temp_s.push_back(v);
  31.     for (int i = 0; i < graph[v].size(); i++) { // перебираем всех соседей
  32.         int u = graph[v][i];
  33.         if (visited[u] == 0) {
  34.             dfs(u, visited, graph);
  35.         }
  36.         else if (visited[u] == 1) {// если сосед на пути от корня до текущей, то мы нашли цикл
  37.             push_ans(u);
  38.             is_cycle = 1;
  39.             return;
  40.         }
  41.     }
  42.     visited[v] = 2; // отмечаем, что вышли из вершины
  43.     temp_s.pop_back();
  44. }
  45. int main()
  46. {
  47.     int n, m;
  48.     cin >> n >> m;
  49.     vector <vector <int>> graph(n);
  50.     int u, v;
  51.     for (int i = 0; i < m; i++) {
  52.         cin >> u >> v;
  53.         u--;
  54.         v--;
  55.         graph[u].push_back(v);
  56.     }
  57.     vector <int> visited(n, 0);// массив из n значений Color.White (0)
  58.     int sz = graph.size();
  59.     for (int i = 0; i < sz; i++) { // перебираем все вершины
  60.         if (visited[i] == 0) {
  61.             dfs(i, visited, graph); // от каждой еще не посещенной запускаем dfs
  62.             if (is_cycle == 1) break;
  63.         }
  64.     }
  65.     if (is_cycle == 0) cout << -1;
  66.     else {
  67.         cout << ans.size() << '\n';
  68.         for (int i = 0; i < ans.size(); i++) {
  69.             cout << ans[i] << " ";
  70.         }
  71.     }
  72.     return 0;
  73. }
RAW Paste Data