C++ Simple DFS O(n^2) Solution


  • 0
    A
        bool dfs(int parent, const vector < vector < int > > &graph, vector < int > &vis) {
            vis[parent] = 1;
            for(auto child : graph[parent]) {
                if(vis[child] == 0) {
                    if(!dfs(child, graph, vis))
                        return false;
                }
                //Back Edge
                if(vis[child] == 1)
                    return false;
            }
            vis[parent] = 2;
            return true;
        }
    
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector < vector < int > > graph(numCourses, vector < int >());
            for(int i = 0; i < prerequisites.size(); i++) 
                graph[prerequisites[i].first].push_back(prerequisites[i].second);
            
            for(int i = 0; i < numCourses; i++) {
                vector < int > vis(numCourses, 0);
                if(!dfs(i, graph, vis)) 
                    return false;
            }
            return true;
        }
    

Log in to reply
 

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