20+ lines C++ BFS/DFS Solutions


  • 41

    Well, this problem is spiritually similar to to Course Schedule. You only need to store the nodes in the order you visit into a vector during BFS or DFS. Well, for DFS, a final reversal is required.


    BFS

    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
            vector<int> degrees = compute_indegree(graph);
            queue<int> zeros;
            for (int i = 0; i < numCourses; i++)
                if (!degrees[i]) zeros.push(i);
            vector<int> toposort;
            for (int i = 0; i < numCourses; i++) {
                if (zeros.empty()) return {};
                int zero = zeros.front();
                zeros.pop();
                toposort.push_back(zero);
                for (int neigh : graph[zero]) {
                    if (!--degrees[neigh])
                        zeros.push(neigh);
                }
            }
            return toposort;
        }
    private:
        vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph(numCourses);
            for (auto pre : prerequisites)
                graph[pre.second].insert(pre.first);
            return graph; 
        }
        vector<int> compute_indegree(vector<unordered_set<int>>& graph) {
            vector<int> degrees(graph.size(), 0);
            for (auto neighbors : graph)
                for (int neigh : neighbors)
                    degrees[neigh]++;
            return degrees;
        }
    };
    

    DFS

    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
            vector<int> toposort;
            vector<bool> onpath(numCourses, false), visited(numCourses, false);
            for (int i = 0; i < numCourses; i++)
                if (!visited[i] && dfs(graph, i, onpath, visited, toposort))
                    return {};
            reverse(toposort.begin(), toposort.end());
            return toposort;
        }
    private:
        vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph(numCourses);
            for (auto pre : prerequisites)
                graph[pre.second].insert(pre.first);
            return graph;
        }
        bool dfs(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited, vector<int>& toposort) { 
            if (visited[node]) return false;
            onpath[node] = visited[node] = true; 
            for (int neigh : graph[node])
                if (onpath[neigh] || dfs(graph, neigh, onpath, visited, toposort))
                    return true;
            toposort.push_back(node);
            return onpath[node] = false;
        }
    };
    

  • 0
    J

    Your code helps me a lot, thanks. I found that in your DFS solution for the Course Schedule problem, “if (visited[node]) return false;” in the dfs_cycle function can be deleted. However, for the Course Schedule II problem, here in the dfs function, if we delete the “if (visited[node]) return false;”, there will be an error. Could you please explain this? Thanks a lot.


  • 1
    Y

    toposort should be a stack to avoid reverse.


  • 0
    C

    return onpath[node] = false; is confusing to me at first. But I guess it's to make the code shorter. At first, I thought onpath[node] = false will evaluate to be true always, but it turns out to return the value of onpath[node], which is assigned as false!


  • 1
    H

    To avoid a final reverse in the DFS solution, you could let graph[pre.first].insert(pre.second) in the make_graph function


  • 0
    Z
    This post is deleted!

  • 2
    B

    Actually I like your clean solution. But for the DFS solution, it took me a while to understand the last part of "dfs" function, which is a little bit confusing for me.

    So based on your code, my understanding is that the "dfs" function returns "false" when everything is "correct" or "node has already been visited", and returns "true" when cycling found on the current path. You combined the "onpath[node] = false" and "return false" together ... and to be honest, I feel that you made this fancy part ONLY because you wanted to shorten the code.

    But in practice, I think using "true" for something "correct" or "works", and "false" for something wrong is more reasonable. So personally, I prefer to change the usage of the "true" and "false" in DFS solution.

    Please let me know if my understanding is wrong. It would be a good learning if anyone points out my wrong understanding of the DFS solution.


  • 1
    Y

    @binchan
    I agree with using TRUE for CORRECT and FALSE for WRONG.
    I modified jianchao's DFS solution a little bit like this.

    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector< vector<int> > graph(numCourses, vector<int>() );
            for(auto item : prerequisites){
                graph[item.second].push_back(item.first);
            }
            vector<int> res;
            vector<bool> visited(numCourses,false), on_path(numCourses,false);
            for(int cid = 0; cid<numCourses; ++cid ){
                if( !visited[cid] && !dfs(res,cid,graph,visited,on_path) ) {
                    // Not visited and can't make dfs without infinite loop
                    return {};
                }
            }
            std::reverse(res.begin(),res.end());
            return res;
        }
    private:
        // Return true if dfs succeed(no cycle).
        bool dfs(vector<int> & res,
            int cid, //course id
            vector< vector<int> > & graph, 
            vector<bool> & visited, 
            vector<bool> & on_path) {
            if(on_path[cid]) return false; // On the same dfs path
            if(visited[cid]) return true; // Visited, no need to go further
            visited[cid] = on_path[cid] = true;
            for(int num : graph[cid]){
                if( on_path[num] || !dfs(res,num,graph,visited,on_path)){
                    // If the node has been on the recursive path,
                    // or call dfs on it return false, we can return false directly
                    // since a cycle has been detected.
                    return false;
                }
            }
            res.push_back(cid); //push current course if all it's children have been added
            on_path[cid] = false; //rewind on_path
            return true;
        }
    };
    

  • 0
    H

    In you last for loop of BFS solution, I think you should add one line

    if (toposort.size() == numCourses)
        break;
    

    So that the algorithm could stop and return as soon as it finds a solution.


  • 0
    S

    beats 99.9%

    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<int> res;
            vector<int> indegree(numCourses,0);
            vector<vector<int>> graph(numCourses,vector<int>());
            
            for(auto pre:prerequisites)
            {
                graph[pre.second].push_back(pre.first);
                indegree[pre.first]++;
            }
            queue<int> que;
            for(int i=0;i<indegree.size();i++)
                if(indegree[i]==0)
                    que.push(i);
                    
            while(!que.empty())
            {
                int u = que.front();que.pop();
                res.push_back(u);
                for(auto v:graph[u])
                {
                    indegree[v]--;
                    if(indegree[v] == 0)
                        que.push(v);
                }
            }
            if(res.size()==numCourses)
                return res;
            else
                return vector<int>();
        }
    };

  • 0
    S

    DFS

    class Solution {
    public:
        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<int> res;
            vector<int> visited(numCourses,0);
            vector<bool> add(numCourses,false);
            vector<vector<int>> graph(numCourses,vector<int>());
            
            for(auto pre:prerequisites)
                graph[pre.second].push_back(pre.first);
            bool cycle=false;
            for(int i=0;i<numCourses ;i++)
            {
                if(visited[i]==0)
                {
                    dfs(graph,i,visited,cycle,res,add);
                    if(cycle==true)
                        return vector<int>();
                }
    
            }
            return res;
           
        }
    private:
        void dfs(vector<vector<int>>& graph,int i,vector<int>& visited,bool& cycle,vector<int>& res, vector<bool>& add)
        {
            if(visited[i]==1){cycle=true;return;}
            if(visited[i]==0)
            {
                visited[i]=1;
                for(auto adj:graph[i])
                {
                    dfs(graph,adj,visited,cycle,res,add);
                }
            }
            visited[i]=2;
            if(visited[i]==2 && add[i]==false)
            {
                res.insert(res.begin(),i);
                add[i] = true;
            }
            
        }
    
    };

  • 0
    V

    @Jian_Bao This is to avoid some repeat numbers


  • 0
    B

    @jianchao.li.fighter The solution is really awesome that, I did understand without the help of comments, nice and neat.


  • 0
    B

    By the way, in DFS, the condition check, !visited[i], can be removed, because it has been included in the dfs block already. Nice, comprehensive solution, tho. Thanks.

    if (!visited[i] && dfs(graph, i, onpath, visited, toposort))
    

  • 0
    A

    I am just wondering that with this approach, which looks clean and this is what I have also done, we beat roughly around 55% submissions only. What other good tricks are used by others to speed up the submissions???


  • 0
    D

    @sutongkui amazing!


Log in to reply
 

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