Could anyone explain why my DFS C++ solution is TLE?


  • 0
    L

    I use visited[] to record each node's state, where 0 means not visited, 1 means being visited and 2 means visited.

    class Solution {
    private:
        bool dfs(int node, vector<unordered_set<int>> adj, vector<int>& visited) {
            if (visited[node] == 2) {
                return true;
            }
            if (visited[node] == 1) {
                return false;
            }
            visited[node] = 1;
            for (auto neighbor : adj[node]) {
                if (!dfs(neighbor, adj, visited)) {
                    return false;
                }
            }
            visited[node] = 2;
            return true;
        }
        
        vector<unordered_set<int>> makeGraph(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> adj(numCourses);
            for (auto prerequisite : prerequisites) {
                adj[prerequisite.second].insert(prerequisite.first);
            }
            return adj;
        }
        
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> adj = makeGraph(numCourses, prerequisites);
            vector<int> visited(numCourses, 0);
            for (int i = 0; i < numCourses; i++) {
                if (!dfs(i, adj, visited)) {
                    return false;
                }
            }
            return true;
        }
    };

  • 0
    G

    Maybe you should pass references of adj in dfs() function.


  • 0
    L

    @guochengc422 Yeah! You are right! Thank you so much!


  • 0
    C

    @guochengc422 because the copy of big adj will cost too much time??? can u explain it for me? ths


  • 0
    G

    @chosenone75 I'm not sure what's the main reason. But the copy of a big set could cost a lot of time and cause TLE. :)


Log in to reply
 

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