Mohammad_Dipu_Sultan

Print a cycle on directed graph

Oct 15th, 2023
1,298
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.12 KB | None | 0 0
  1. // If there is multiple cycle print any of them, graph will be directed graph
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. vector<int>adj[100], cycle;
  5. int vis[100], pathvis[100];
  6.  
  7. int dfs(int node){
  8.     vis[node] = 1;
  9.     pathvis[node] = 1;
  10.     cycle.push_back(node);
  11.  
  12.     for(auto it: adj[node]){
  13.         if(pathvis[it] == 1){
  14.             // Cycle found
  15.             int startindex = 0;
  16.             while(cycle[startindex]!=it){
  17.                 startindex++;
  18.             }
  19.  
  20.             for(int i = startindex; i <cycle.size(); i++){
  21.                 cout << cycle[i] << " ";
  22.             }
  23.             cout << it << endl;
  24.  
  25.             return true; // Stop DFS after finding the first cycle
  26.         }
  27.         else if(vis[it] == 0){
  28.             if(dfs(it)==true){
  29.                 return true; // Stop DFS early if a cycle is found
  30.             }
  31.         }
  32.     }
  33.     pathvis[node] = 0;
  34.     cycle.pop_back();
  35.     return false;
  36. }
  37. int main(){
  38.  
  39.     int v, e;
  40.     cin >> v >> e;
  41.  
  42.     for(int i = 0; i < e; i++){
  43.         int x, y;
  44.         cin >> x >> y;
  45.         adj[x].push_back(y);
  46.     }
  47.     memset(vis, 0, sizeof(vis));
  48.     memset(pathvis, 0, sizeof(pathvis));
  49.  
  50.     for(int i = 0; i < v; i++){
  51.         if(vis[i] == 0){
  52.             cycle.clear();
  53.             dfs(i);
  54.             break; //Stop after finding the first cycle
  55.         }
  56.     }
  57.  
  58.     return 0;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment