Friday, 20 February 2026

check if a cycle exists usign kahn's Algo or Topological sort(Accpted soln in GFG)

 class Solution {

  public:

    vector<int> toposort(vector<vector<int>>&adj,int V){

        vector<int>count(V,0);

        queue<int>q;

        vector<int>visited;

        for(int i=0;i<V;i++){

            for(int x:adj[i]){

                count[x]++;

            }

        }

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

        while(!q.empty()){

            int x=q.front();

            q.pop();

            visited.push_back(x);

            for(int y:adj[x]){

                count[y]--;

                if(count[y]==0)q.push(y);

           }

        }

        return visited;

    }

    bool isCyclic(int V, vector<vector<int>> &edges) {

        // code here

        vector<vector<int>> adj(V);

        for(auto& e : edges){

            adj[e[0]].push_back(e[1]);

        }

        vector<int>ans=toposort(adj,V);

        if(ans.size()==adj.size()) return false;

        else return true;

        

    }

};

No comments:

Post a Comment

SDE floyd-warshall algorithm

 // User function template for C++ class Solution {   public:     void floydWarshall(vector<vector<int>> &dist) {         //...