Easy C++ dfs Solution


  • 4
    J
    class Solution {
    bool isCycle(vector<list<int>>& g, vector<bool>& visited, vector<bool>& rec, int n) {
        if(visited[n] == false) {
            visited[n] = true;
            rec[n] = true;
            
            for(auto iter = g[n].begin(); iter != g[n].end(); ++iter) {
                if(isCycle(g, visited, rec, *iter))
                    return true;
                if(rec[*iter])
                    return true;
            }
            
            rec[n] = false;
        }
        
        return false;
    }
    
    public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<list<int> > g(numCourses, list<int>());
        for(int i = 0; i<prerequisites.size(); i++)
            g[prerequisites[i].first].push_back(prerequisites[i].second);
            
        vector<bool> visited(prerequisites.size(), false);
        vector<bool> rec(prerequisites.size(), false);
        
        for(int i = 0; i<g.size(); i++)
            if(isCycle(g, visited, rec, i))
                return false;
    
        return true;
      }
    };

  • 0
    P

    nice solution!


  • 0
    A

    in function canFinish

    vector<bool> visited(prerequisites.size(), false);

    vector<bool> rec(prerequisites.size(), false);

    should be

    vector<bool> visited(numCourses, false);

    vector<bool> rec(numCourses, false);

    am i right?


  • 0
    J

    No. The prerequisite vector could contain like this: [1, 0], [2, 0], [3, 0], [2, 1], [3, 2]. In this case, we have 4 courses, but the length of the vector is 5.


Log in to reply
 

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