Kahn's algo variation


#1
bool isCycle( vector<vector<int> > adj, int n)
{
queue<int> q;
vector<int> indegree(n+1,0); 
for(int i=0; i<=n; i++) 
    for(auto it: adj[i])
         indegree[it]++;   //count indegrees

for(int i=0; i<indegree.size(); i++)
     if(indegree[i]==0)
        q.push(i);     //least indegrees element pushed for topo sort 

int c=0; //count of nodes for indegree
while(q.size()) //queue must not be empty
{
    int curNode=q.front();
    q.pop();
    c++; //a node
    for(auto it: adj[curNode])
    {
        indegree[it]--;
        if(indegree[it]==0)
            q.push(it);
    }
}
return (c==n+1?false:true);  /**/counts of topo=no of total nodes means we have indegree elements so there is no loop**
}

int Solution::solve(int n, vector<vector<int> > &a) {
if(n<=2) return 0;
 vector<vector<int> > adj(n+1);
 for(int i=0; i<a.size(); i++)
 {
     adj[a[i][0]].push_back(a[i][1]);  //directed adj list
     
 }
return isCycle(adj,n);
 
}