Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
937 B
0
Indexable
#include<map>
#include<list>
#include<queue>
#include<vector>

detecting cycle in Directed using kahns algo

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 -1;
        int y=edges[i].second -1;
        adjlist[x].push_back(y);
       // adjlist[y].push_back(x);

    }
    queue<int> q;
    vector<int> degree(n);
    for(auto i:adjlist){
      for(auto j:i.second){
        degree[j]++;
      }
    }

    for(int i=0;i<n;i++){
      if(degree[i]==0) q.push(i);
    }

    int cnt=0;
    while(!q.empty()){
      int front=q.front();
      q.pop();
      cnt++;
      for(auto nbr:adjlist[front]){
        degree[nbr]--;
        if(degree[nbr]==0) q.push(nbr);
      }
    }
    if(cnt==n) return false;
    if(cnt!=n) return true;

}