Advertisement
Oppenheimer

Cycle in directed graph

Aug 19th, 2022
29
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.14 KB | None | 0 0
  1. int n;
  2. vector<vector<int>> adj;
  3. vector<char> color;
  4. vector<int> parent;
  5. int cycle_start, cycle_end;
  6.  
  7. bool dfs(int v) {
  8.     color[v] = 1;
  9.     for (int u : adj[v]) {
  10.         if (color[u] == 0) {
  11.             parent[u] = v;
  12.             if (dfs(u))
  13.                 return true;
  14.         } else if (color[u] == 1) {
  15.             cycle_end = v;
  16.             cycle_start = u;
  17.             return true;
  18.         }
  19.     }
  20.     color[v] = 2;
  21.     return false;
  22. }
  23.  
  24. void find_cycle() {
  25.     color.assign(n, 0);
  26.     parent.assign(n, -1);
  27.     cycle_start = -1;
  28.  
  29.     for (int v = 0; v < n; v++) {
  30.         if (color[v] == 0 && dfs(v))
  31.             break;
  32.     }
  33.  
  34.     if (cycle_start == -1) {
  35.         cout << "Acyclic" << endl;
  36.     } else {
  37.         vector<int> cycle;
  38.         cycle.push_back(cycle_start);
  39.        
  40.        
  41.         for (int v = cycle_end; v != cycle_start; v = parent[v])
  42.             cycle.push_back(v);
  43.        
  44.        
  45.         cycle.push_back(cycle_start);
  46.         reverse(cycle.begin(), cycle.end());
  47.  
  48.         cout << "Cycle found: ";
  49.         for (int v : cycle)
  50.             cout << v << " ";
  51.         cout << endl;
  52.     }
  53. }
  54.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement