Advertisement
Guest User

Untitled

a guest
Nov 14th, 2018
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4.  
  5. using namespace std;
  6.  
  7. bool dfs(int v, vector<int>& color, vector<vector<int>>& graph, vector<int>& p, int &cycleEnd, int &cycleSt) {
  8.     color[v] = 1;
  9.     for (int i = 0; i < graph[v].size(); ++i) {
  10.         int to = graph[v][i];
  11.         if (color[to] == 0) {
  12.             p[to] = v;
  13.             if (dfs(to, color, graph, p, cycleEnd, cycleSt))  return true;
  14.         }
  15.         else if (color[to] == 1) {
  16.             cycleEnd = v;
  17.             cycleSt = to;
  18.             return true;
  19.         }
  20.     }
  21.     color[v] = 2;
  22.     return false;
  23. }
  24.  
  25. bool find_cycle(vector<vector<int>>& graph, vector <int> &cycle) {
  26.     int n = graph.size();
  27.     vector<int> color(n, 0);
  28.     vector<int> p(n, -1);
  29.     int cycleSt, cycleEnd;
  30.     cycleSt = -1;
  31.     for (int i = 0; i < n; ++i)
  32.         if(!color[i])
  33.             if (dfs(i, color, graph, p, cycleEnd, cycleSt))
  34.                 break;
  35.     if (cycleSt == -1)
  36.         return false;
  37.     else {
  38.         cycle.push_back(cycleSt);
  39.         for (int v = cycleEnd; v != cycleSt; v = p[v])
  40.             cycle.push_back(v);
  41.         reverse(cycle.begin(), cycle.end());
  42.         return true;
  43.     }
  44.  
  45. }
  46.  
  47. int main() {
  48.     int n, m;
  49.     cin >> n >> m;
  50.     vector < vector<int> > graph(n);
  51.     vector <int> cycle;
  52.     for (int i = 0; i < m; ++i) {
  53.         int firstV, secondV;
  54.         cin >> firstV >> secondV;
  55.         graph[firstV - 1].push_back(secondV - 1);
  56.     }
  57.     if (find_cycle(graph,cycle)) {
  58.         cout << "YES" << endl;
  59.         for (int i = 0; i < cycle.size(); ++i)
  60.             cout << cycle[i] + 1 << ' ';
  61.     }
  62.     else
  63.         cout << "NO";
  64.     //system("pause");
  65.     return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement