Beats 100 % . Easy DFS


  • 0
    A
    class Solution {
    public:
        bool checkcycle(vector<vector<int>> &g,int u,int  *vis,int *path)
        {
            vis[u]=1;
            path[u]=1;
            for(auto x: g[u])
            {
                if(path[x]) return true;
                if(!vis[x] && checkcycle(g,x,vis,path)) return true;
            }
            path[u]=0;
            return false;
            
        }
        bool canFinish(int numCourses, vector<pair<int, int>>& p) {
            vector<vector<int>> g(numCourses);
            for(auto x:p)
            {
                g[x.second].push_back(x.first);
            }
            int vis[numCourses];
            int path[numCourses];
            for(int i=0;i<numCourses;i++) vis[i]=0,path[i]=0;
            for(int i=0;i<numCourses;i++)
                if(!vis[i] && checkcycle(g,i,vis,path)) return false;
            return true;
            
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.