Share C++ solution beating 100% and why unordered_set still works in the BFS solution?


  • 0
    C

    It's the same idea as

    https://leetcode.com/discuss/35847/short-and-simple

    I had thought we have to use set due to the insertion in the while loop. However, using unordered_set still works and increases the efficiency to be 100% faster than other C++ solutions. Anybody knows why? Doesn't unordered_set specify the order? Thanks

        vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        map<int,unordered_set<int>> suc, pre;
        for (auto p: prerequisites)
        {
            suc[p.second].insert(p.first);
            pre[p.first].insert(p.second);
        }
        
        unordered_set<int> cs;
        for (int i=0;i<numCourses; i++)
           cs.insert(i);
           
        for (auto p: pre)
        {
            cs.erase(p.first);
        }
    
        vector<int> res;
        
        while(cs.size())
        {
            int a=*cs.begin();
            res.push_back(a);
            cs.erase(a);
            for(auto b: suc[a])
            {
                pre[b].erase(a);
                if (pre[b].empty())
                   cs.insert(b);
            }
        }
        
        if(res.size()!=numCourses)
           res.clear();
        
        return res;
    }

  • 0
    U

    Maybe Leetcode changed the algorithm that calculated run time.


Log in to reply
 

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