Detecting Cycles in a Directed Graph using Kahn’s Algorithm (Topological Sort)

In graph theory, detecting cycles in a directed graph is a common problem with applications in scheduling, dependency resolution, and compiler design. One efficient way to solve this is using Kahn’s Algorithm, which is based on topological sorting.

Detecting Cycles in a Directed Graph using Kahn’s Algorithm (Topological Sort)

---

 Idea

• We count how many nodes can be sorted topologically.

• If we can sort all nodes → the graph is acyclic.

• If some nodes remain due to incoming edges → the graph has a cycle.

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Solution {
  public:
    bool isCyclic(int V, vector<vector<int>> &edges){
        vector<vector<int>> adj(V);
        vector<int> indeg(V, 0);
        
        for(int i=0;i<edges.size();i++){
            int u=edges[i][0];
            int v=edges[i][1];
            adj[u].push_back(v);
            indeg[v]++;
        }

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

        int count=0;
        while(!q.empty()){
            int temp=q.front();
            q.pop();
            count++;

            for(int i=0;i<adj[temp].size();i++){
                int temp1=adj[temp][i];
                indeg[temp1]--;
                if(indeg[temp1]==0){
                    q.push(temp1);
                }
            }
        }

        return V!=count;
    }
};

int main() {
    vector<vector<int>> edges = {
        {0, 1}, {1, 2}, {2, 3}, {3, 1}
    };

    int V = 4;

    Solution s;
    cout << (s.isCyclic(V, edges) ? "Cycle Detected" : "No Cycle") << endl;
    return 0;
}

 Input
V = 4
edges = { {0,1}, {1,2}, {2,3}, {3,1} }
Output
Cycle Detected

Time and Space Complexity

• Time: O(V + E)

• Space: O(V)