Advertisement
Singasking

Untitled

Oct 8th, 2022 (edited)
196
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.94 KB | None | 0 0
  1. //DFS all possible cycle detection
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. const int N=10e3;
  5. vector<vector<int>> paths;
  6. vector<int> adj[N];
  7. bool vis[N];
  8. void dfs(int org,int src,int parent,int visitcount,int V,vector<int> path) {
  9. vis[src]=true;
  10. visitcount++;
  11. path.push_back(src);
  12. for(auto x:adj[src]) {
  13. if(x==parent) { continue; }
  14. if(vis[x]==true &&x==org) { path.push_back(x); paths.push_back(path); }
  15. if(vis[x]==false) { dfs(org,x,src,visitcount,V,path); }
  16. }
  17. vis[src]=false;
  18. }
  19. int main() {
  20. int V,E;
  21. cin>>V>>E;
  22. for(int i=0;i<E;i++) {
  23. int x,y;
  24. cin>>x>>y;
  25. adj[x].push_back(y);
  26. adj[y].push_back(x);
  27. }
  28. vector<int> path;
  29. for(int i=0;i<=V;i++) {
  30.  
  31. dfs(i,i,-1,0,V,path);
  32. }
  33. if(paths.size()==0) {
  34. cout<<"No cycle found"<<endl;
  35. } else {
  36. for(auto x:paths) {
  37. for(auto y:x) {
  38. cout<<y<<" ";
  39. }
  40. cout<<endl;
  41. }
  42. }
  43. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement