C++ 260ms DFS with Buffer


  • 0
    S

    class Solution {

    bool helper(const vector<unordered_set<int> >& links, unordered_set<int>& path, vector<bool> & buffer, int node)
    {
        if (buffer[node]) return true;
        if (path.find(node) != path.end() ) return false;
        
        if ( links[node].empty() ) return true;
        
        path.insert(node);
    
        unordered_set<int>::const_iterator itr = links[node].begin();
        for(; itr!= links[node].end(); ++itr)
        {
            bool result = helper(links, path, buffer, *itr);
            if (result == true)
                buffer[*itr] = true;
            else
                return false;
        }
        path.erase(node);
        return true;
    
    }
    

    public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {

        if (numCourses <2) return true;
        
        vector<unordered_set<int> > links(numCourses);
        
        //build the graph
        for(int i=0; i<prerequisites.size(); i++)
            links[prerequisites[i].first].insert(prerequisites[i].second);
    
        // whether this node has been checked
        vector<bool> buffer(numCourses, false);
        
        unordered_set<int> path;
        for(int i=0; i<links.size(); i++)
        {
            if (helper(links, path, buffer, i) == false)
                return false;
            
            buffer[i] = true;
        }
        
        return true;
    }
    

    };**


Log in to reply
 

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