Why C++ solution is slower than PYTHON? 500ms vs 72ms


  • 1
    O
    class Solution {
    private:
    vector<vector<int>> graph;
    vector<int> count_in;
    
    public:
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        graph.resize(numCourses, vector<int>());
        count_in.resize(numCourses, 0);
    
        for (auto p : prerequisites){
            count_in[p.first]++; 
            graph[p.second].push_back(p.first);
        }
    
        vector<int> ans;
        for (int i = 0; i < numCourses; i++) 
            if (count_in[i] == 0) ans.push_back(i);
    
        for(int cur = 0; cur < ans.size(); cur++){
            for (auto it = graph[ans[cur]].begin(); it != graph[ans[cur]].end(); it++){
                count_in[*it]--;
                if (count_in[*it] == 0) ans.push_back(*it);
            }
        }
    
        return (ans.size() == numCourses) ? ans : vector<int>();
    }
    };

Log in to reply
 

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