Given a Directed Graph. Check whether it contains any cycle or not.

Explanation with Code
bool hasCycle(vector<vector<int>>& adj, vector<int>& vis, int curr){
    if(vis[curr] == 2)
        return true;
    
    vis[curr] = 2;
    for(int i=0; i<adj[curr].size(); i++){
        if(vis[adj[curr][i]] != 1 and hasCycle(adj, vis, adj[curr][i]))
            return true;
    }
    
    vis[curr] = 1;
    return false;
}
int Solution::solve(int edges, vector<vector<int>> &arr) {
    int n = arr.size();
    vector<vector<int>> adj(edges+1);
    
    for(int i=0; i<n; i++)
        adj[arr[i][0]].push_back(arr[i][1]);
    
    vector<int> vis(edges+1, 0);
    for(int i=1; i<=edges; i++){
        if(vis[i] == 0 and hasCycle(adj, vis, i))
            return 1;
    }
    return 0;
}


Write a comment