18-22 lines C++ BFS/DFS Solutions


  • 126

    As suggested by the hints, this problem is equivalent to detecting a cycle in the graph represented by prerequisites. Both BFS and DFS can be used to solve it using the idea of topological sort. If you find yourself unfamiliar with these concepts, you may refer to their wikipedia pages. Specifically, you may only need to refer to the link in the third hint to solve this problem.

    Since pair<int, int> is inconvenient for the implementation of graph algorithms, we first transform it to a graph. If course u is a prerequisite of course v, we will add a directed edge from node u to node v.


    BFS

    BFS uses the indegrees of each node. We will first try to find a node with 0 indegree. If we fail to do so, there must be a cycle in the graph and we return false. Otherwise we have found one. We set its indegree to be -1 to prevent from visiting it again and reduce the indegrees of all its neighbors by 1. This process will be repeated for n (number of nodes) times. If we have not returned false, we will return true.

    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
            vector<int> degrees = compute_indegree(graph);
            for (int i = 0; i < numCourses; i++) {
                int j = 0;
                for (; j < numCourses; j++)
                    if (!degrees[j]) break;
                if (j == numCourses) return false;
                degrees[j] = -1;
                for (int neigh : graph[j])
                    degrees[neigh]--;
            }
            return true;
        }
    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

    For DFS, it will first visit a node, then one neighbor of it, then one neighbor of this neighbor... and so on. If it meets a node which was visited in the current process of DFS visit, a cycle is detected and we will return false. Otherwise it will start from another unvisited node and repeat this process till all the nodes have been visited. Note that you should make two records: one is to record all the visited nodes and the other is to record the visited nodes in the current DFS visit.

    The code is as follows. We use a vector<bool> visited to record all the visited nodes and another vector<bool> onpath to record the visited nodes of the current DFS visit. Once the current visit is finished, we reset the onpath value of the starting node to false.

    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
            vector<bool> onpath(numCourses, false), visited(numCourses, false);
            for (int i = 0; i < numCourses; i++)
                if (!visited[i] && dfs_cycle(graph, i, onpath, visited))
                    return false;
            return true;
        }
    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_cycle(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited) {
            if (visited[node]) return false;
            onpath[node] = visited[node] = true; 
            for (int neigh : graph[node])
                if (onpath[neigh] || dfs_cycle(graph, neigh, onpath, visited))
                    return true;
            return onpath[node] = false;
        }
    };

  • 2
    S

    good job! And clear explanation!


  • 6

    Thank you for your solution and explanation. I have a question, in your DFS solution,

     bool dfs_cycle(vector<unordered_set<int>>& graph, int node, vector<bool>& onpath, vector<bool>& visited) {
            if (visited[node]) return false;
    

    I did not understand the meaning of if (visited[node]) return false;. Is this sentence needed? Thank you very much.


  • 1

    Good! It is unnecessary since I have checked for that in canFinish by !visited[i].


  • 0
    D
    This post is deleted!

  • 1

    Yes, it's strongly suggested to read through the wiki for Kahn's algorithm. With it, it's easy to get this problem done.


  • 0
    W
    This post is deleted!

  • 0

    beautiful implementation !


  • 1

    Your DFS solution seems can not AC .....


  • 0

    @RainbowGuy Have you rewritten/copied it correctly? I have just tested and it got accepted as before.


  • 0
    K

    If we remove it then many nodes may be visited several times by dfs.


  • 0

    In dfs_cycle, if (visited[node]) return false; is not necessary.


  • 0

    @RainbowSecret You need to pass references of arguments of the dfs_cycle function to avoid TLE


  • 8
    B

    @暁美焔
    Actually if (visited[node]) return false; is not necessary, but we use it to prune the recursion tree. The time complexity will largely increase without this clause.


  • 0
    W

    Thanks for the great solution. I changed your "unordered_set" to "multiset" and the code got faster, any ideas why?


  • 0
    A

    nevermind.. what i mentioned wouldn't work.


  • 0
    L

    @wizowizo unordered_set-->implemented by hash, multiset--->implemented by red-black-tree (one of AVG tree )


  • 0
    Q

    @jianchao.li.fighter I think it can save much running time if you add this sentence.


  • 5

    @Burlesque1 @jianchao-li-fighter @qinghui @SniperLi

    if (visited[node]) return false; is definitely necessary!!! I remove this line in my java implementation, it increased from 5ms to 185ms.

    This line prevents you from visiting other already validated DAG again. When you enter a DAG already visited, the result is obvious: can find a cycle in a DAG?

    Think about this instance:

    DAG3 <- ... <- DAGk
    |---> (DAG2 ->DAG1)
    // in fact, (DAG2 ->DAG1) can be treated as a big DAG if you fortunately started from a node in DAG2. :-)

    If you validate node in a DAG with order of k, k-1, ... , 2, 1, guess what? If you DFS from a node in DAGk, you will check through DAGk-1...DAG1 without this line.

    It's dumb, right?

    BFS or Khan's algorithm is O(v^2)
    DFS is O(v)


  • 0
    Z

    I come up with the same solution as yours,but what's the time complexity of your solution? Is it O(n^2)? Since you have two foo loop. But wiki says the time complexity is O(n+e) while e is the number of edges.So I'm confused now.


Log in to reply
 

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