I am getting a TLE error while performing cycle detection

Question

I have written a code to the leetcode problem(courseSchedule) which basically asks whether a given set of courses can be done given dependencies. my approach is to create a graph and then check for a cycle, however, it's giving a TLE error. Can you help me as to why is the TLE happening or if there's a better approach that I can use ?

bool cycle( vector<vector<int>> &adj,int i,vector<bool> vis){
    
    if(vis[i])
        return true;
    
    vis[i]=true;
    
    for(int k=0;k<adj[i].size();k++)
       if(cycle(adj,adj[i][k],vis))
           return true;
    
    return false;
}

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        vector<vector<int>> adj(numCourses);
        
        for(int i=0;i<prerequisites.size();i++)
            adj[prerequisites[i][1]].push_back(prerequisites[i][0]);
        
        vector<bool> vis(numCourses,false);
        
        for(int i=0;i<numCourses;i++)
            if(cycle(adj,i,vis))
                return false;
        
        return true;
    }
};

Answer 1

Actually, your function is correct but so inefficient.

This is because in the cycle function performs so many redundant operations i.e check for the same node multiple times.

Your Code:

bool cycle( vector<vector<int>> &adj,int i,vector<bool> vis){
    
    if(vis[i])
        return true;
    
    vis[i] = true;
    
    for(int k = 0; k < adj[i].size(); k++)
       
       if(cycle(adj, adj[i][k], vis))
           return true;
    
    return false;
}

Ex:

0 ---> 1 ---> 2 ......... (some more edges)

0 ---> 3 ---> 2 ---> 4 ........ (some more edges)

So, for this graph, for the start vertex 0 (with your code) for the bool function:

iteration - 1: you perform the DFS and check for 1 and 2 and ......

iteration - 2: you perform the DFS and check for 3 and again 2 .....

So, like this, you will be recomputing the same sub-problems. To avoid this you need to put another array just check if a node is already computed.

So I have introduced another vector var (initialized to false) which basically sets to true if node is visited and got approved as non-cycle node (which doesn't involve in a cycle) .

Improved Code:

bool cycle( vector<vector<int>> &adj,int i,vector<bool> vis, vector<bool>& var){
    
    // if i involves in cycle and visited in the current sequence
    if(!var[i] and vis[i])
        return true;
    
    vis[i] = true;
    
    for(int k=0;k<adj[i].size();k++) {
       
       // if adj[i][k] is true i.e doesn't involve in cycle, so no need to check it. If it is false we should check it.
       if(!var[adj[i][k]] and cycle(adj,adj[i][k],vis, var))
           return true;
       else 
        var[adj[i][k]] = true; // else setting true to tell it doesn't involve in cycle
    }

    // setting true to tell it doesn't involve in cycle
    var[i] = true;
    
    return false;
}


class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        
        vector<vector<int>> adj(numCourses);
        
        for(int i=0;i<prerequisites.size();i++)
            adj[prerequisites[i][1]].push_back(prerequisites[i][0]);
        
        vector<bool> vis(numCourses,false);
        vector<bool> var(numCourses,false);
        
        for(int i=0;i<numCourses;i++)
            if(cycle(adj,i,vis, var))
                return false;
        
        return true;
    }
};

Note:

I just made small changes to make your code overcome TLE without changing the basic logic. But this is still inefficient as your logic needs to pass the vector by value. I suggest you think another way :)