Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
973 B
1
Indexable
Never
#include<map>
#include<list>
#include<vector>
bool  dfs(int node,map<int,list<int>> &adjlist,map<int,bool> &vis,vector<bool> &stack ){
  vis[node]=true;
  stack[node]=true;
  for(auto nbr:adjlist[node]){
    
    if(!vis[nbr]){
      bool foundfs=dfs(nbr,adjlist,vis,stack);
      if(foundfs==true) return true;


    }else if(stack[nbr]==true) return true;
  }
  stack[node]=false;
  return false;
}



int detectCycleInDirectedGraph(int n, vector < pair < int, int >> & edges) {
  map<int,list<int>> adjlist; //making adj list
    for(int i=0;i<edges.size();i++){   //edges.size()
        int x=edges[i].first;
        int y=edges[i].second;
        adjlist[x].push_back(y);
       // adjlist[y].push_back(x);

    }
    map<int,bool> vis;
    vector<bool> stack(n,false);
    for(int i=0;i<n;i++){
      if(!vis[i]){
        bool check=dfs(i,adjlist,vis,stack);
        if(check) return true;
      }
    }
    return false;
   
}