Does anyone know why my c++ code time exceeds?


  • 0

    Here is my solution:

    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            // unordered_map<int, vector<int>> graph = makeGraph(numCourses, prerequisites);
            vector<unordered_set<int>> graph = makeGraph(numCourses, prerequisites);
            unordered_set<int> visited, onPath;
            for (int i=0; i<numCourses; i++){
                if (visited.find(i)==visited.end()){ 
                    if(topoSort(visited, graph, i, onPath)) return false;
                }
            }
            return true;
        }
    
    private:
        vector<unordered_set<int>> makeGraph(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 topoSort(unordered_set<int> visited, vector<unordered_set<int>> &graph, int node, unordered_set<int> onPath){
            // if (visited.find(node)!=visited.end()) return true;
            visited.insert(node), onPath.insert(node);
            for (auto neighbor : graph[node]){
                if (onPath.find(neighbor)!=onPath.end() || topoSort(visited, graph, neighbor, onPath)){
                    return true;
                }
            }
            onPath.erase(node);
            return false;
        }
    };
    

    I am new in C++. I used unordered set to store the nodes that have been visited and visited along the current path. The logic seems correct, but it returns time exceeds when I submit the code. Can anyone help me with the issue? Thanks!!


  • 0

    @Belle.ro I figured it out by myself. I forgot the '&' symbol in topoSort function. C++ pass parameters by value by default, but I need to pass the parameters by reference, so I need to add '&' before the parameters.


Log in to reply
 

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