Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //DFS all possible cycle detection
- #include <bits/stdc++.h>
- using namespace std;
- const int N=10e3;
- vector<vector<int>> paths;
- vector<int> adj[N];
- bool vis[N];
- void dfs(int org,int src,int parent,int visitcount,int V,vector<int> path) {
- vis[src]=true;
- visitcount++;
- path.push_back(src);
- for(auto x:adj[src]) {
- if(x==parent) { continue; }
- if(vis[x]==true &&x==org) { path.push_back(x); paths.push_back(path); }
- if(vis[x]==false) { dfs(org,x,src,visitcount,V,path); }
- }
- vis[src]=false;
- }
- int main() {
- int V,E;
- cin>>V>>E;
- for(int i=0;i<E;i++) {
- int x,y;
- cin>>x>>y;
- adj[x].push_back(y);
- adj[y].push_back(x);
- }
- vector<int> path;
- for(int i=0;i<=V;i++) {
- dfs(i,i,-1,0,V,path);
- }
- if(paths.size()==0) {
- cout<<"No cycle found"<<endl;
- } else {
- for(auto x:paths) {
- for(auto y:x) {
- cout<<y<<" ";
- }
- cout<<endl;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement