Untitled

mail@pastecode.io avatar
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";
}