Untitled
unknown
plain_text
a year ago
1.5 kB
1
Indexable
Never
#include<map> #include<queue> #include<list> bool bfs(int node,map<int,list<int>>&adjlist,map<int,bool> &vis,map<int,int> &parent){ queue<int> q; vis[node]= true; parent[node]=-1; q.push(node); while(!q.empty()){ int front=q.front(); q.pop(); for(auto i:adjlist[front]){ if(vis[i] && parent[front]!=i){ //visited but not the parent of current node(front) then cycle return true; }else if(!vis[i]){ q.push(i); vis[i]=true; parent[i]=front; } } } return false; } bool cycdfs(int node,int parent,map<int,list<int>>&adjlist,map<int,bool> &vis){ vis[node]=true; for(auto nbr:adjlist[node]){ if(!vis[nbr]){ bool cycdet=cycdfs(nbr,node,adjlist,vis); if(cycdet) return true; }else if(vis[nbr] && nbr!=parent) return true; } return false; } string cycleDetection (vector<vector<int>>& edges, int n, int m) { bool check; map<int,list<int>> adjlist; //making adj list for(int i=0;i<m;i++){ //edges.size() int x=edges[i][0]; int y=edges[i][1]; adjlist[x].push_back(y); adjlist[y].push_back(x); } map<int,bool> vis; map<int,int> parent; for(int i=0;i<n;i++){ if(!vis[i]){ check=cycdfs(i,-1,adjlist,vis); if(check==true) return "Yes"; } } return "No"; }