Advertisement
Mohammad_Dipu_Sultan

Print all cycle

Oct 15th, 2023
1,036
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. // Print all cycle if there multiple cycle exist
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4.  
  5. vector<int>adj[111], cycle;
  6. int vis[111], pathvis[111];
  7.  
  8. int dfs(int node){
  9.     vis[node] = 1;
  10.     pathvis[node] = 1;
  11.     cycle.push_back(node);
  12.  
  13.     for(auto it: adj[node]){
  14.         if(pathvis[it] == 1){
  15.             int startIndex = 0;
  16.             while(cycle[startIndex] != it){
  17.                 startIndex++;
  18.             }
  19.             for(int i = startIndex; i < cycle.size(); i++){
  20.                 cout << cycle[i] << " ";
  21.             }
  22.             cout << endl;
  23.         }
  24.         else if(vis[it] == 0){
  25.             if(dfs(it) == true){
  26.                 return true;
  27.             }
  28.         }
  29.     }
  30.     pathvis[node] = 0;
  31.     cycle.pop_back();
  32.     return false;
  33. }
  34. int main(){
  35.     int v, e;
  36.     cin >> v >> e;
  37.     for(int i = 0; i < e; i++){
  38.         int x, y;
  39.         cin >> x >> y;
  40.         adj[x].push_back(y);
  41.     }
  42.     memset(vis, 0, sizeof(vis));
  43.     memset(pathvis, 0, sizeof(pathvis));
  44.  
  45.     for(int i = 0; i < v; i++){
  46.         if(vis[i] == 0){
  47.             dfs(i);
  48.         }
  49.     }
  50.     return 0;
  51. }
  52.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement