Why does my code take 166ms? Can any one help me?


  • 0
    X

    class Solution {
    public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
    map<int,int> map;
    vector<unordered_set<int>> matrix(numCourses);
    unordered_set<int> set;

        for (auto a:prerequisites)
        {
            if ( matrix[a.second].find(a.first) == matrix[a.second].end())
            {
                map[a.first]++;
                matrix[a.second].insert(a.first);
                set.insert(a.first);
                set.insert(a.second);
            }            
        }
        while(1)
        {
            int index=0; 
            auto iter= set.begin();
            for (iter = set.begin(); iter!=set.end() && map[*iter]>0; iter++) {}  //find the iter with in-degree == 0
            if (iter!=set.end())
            {
                for (auto it = matrix[*iter].begin(); it != matrix[*iter].end(); it++)  //update in-degree
                {
                    map[*it]--;
                }
                set.erase(*iter);
            }
            else if (set.size() > 0) return false;
            else return true;
        }
    }
    

    };

    My code is similar to the BFS solution in https://discuss.leetcode.com/topic/13441/bfs-topological-sort-and-dfs-finding-cycle-by-c, and I also tried to reduce the iterations via storing all the candidate nodes (the nodes haven't been processed). Can any one point me out why my solution takes 166ms? Where is the major time cost?
    Thanks


Log in to reply
 

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