« back

Detect cycle in an directed graph

Tags : dfs, bfs, graph, geeksforgeeks, cpp, medium

Problem Statement - link #

Given a Directed Graph with V vertices (Numbered from 0 to V-1) and E edges, check whether it contains any cycle or not.

Your Task: You dont need to read input or print anything. Your task is to complete the function isCyclic() which takes the integer V denoting the number of vertices and adjacency list as input parameters and returns a boolean value denoting if the given directed graph contains a cycle or not.

Expected Time Complexity: O(V+E)
Expected Auxiliary Space: O(V)

Examples #

Example 1:

Input:  


Output: 1
Explanation: 3 -> 3 is a cycle

Constraints #

Solutions #

class Solution
{
    public:
    vector<int> indegreeUtil(int V,vector<int> adj[]){
        vector<int> ind(V);
        for(int i=0;i<V;i++)
            for(int j: adj[i])
                ind[j]++;
        return ind;
    }
    // Function to detect cycle in a directed graph.
    bool isCyclic(int V, vector<int> adj[]) {
        // code here
        queue<int> q;
        vector<int> ind = indegreeUtil(V,adj);
        for(int i=0;i<V;i++)
            if(!ind[i])
                q.push(i);
        int count = 0;
        while(!q.empty()){
            int u = q.front(); q.pop();
            count++;
            for(int v: adj[u]){
                ind[v]--;
                if(!ind[v])
                    q.push(v);
            }
        }
        return V!=count;
    }
};