BFS 23 lines


  • 0
    P
    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            unordered_map<int, int> deg;
            unordered_map<int, unordered_set<int>> graph;
            for(auto pre : prerequisites){
                if(!deg.count(pre.first))   deg[pre.first] = 0;
                if(!graph[pre.first].count(pre.second)){
                    graph[pre.first].insert(pre.second);
                    deg[pre.second]++;
                }
            }
            queue<int> buf;
            for(auto& it : deg)
                if(it.second == 0)
                    buf.push(it.first);
            int res = 0, tmp = 0;
            while(!buf.empty()){
                tmp = buf.front();
                res++;
                buf.pop();
                for(auto& neigh : graph[tmp]){
                    if(!--deg[neigh])
                        buf.push(neigh);
                }
            }
            return res == deg.size();
        }
    };
    

Log in to reply
 

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