15 lines concise and easy understand c++ solution toposort


  • 0
    A
    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph(numCourses, unordered_set<int>());
            vector<int> indegree(numCourses, 0);
            for(auto pre : prerequisites){
                if(graph[pre.second].count(pre.first) == 0){
                    graph[pre.second].insert(pre.first);
                    indegree[pre.first]++;
                }
            }
            for(int i = 0, j = 0; i < numCourses; i++){
                for(j = 0; j < numCourses; j++) if(indegree[j] == 0) break;
                if(j == numCourses) return false;
                indegree[j]--;
                for(auto p : graph[j]) indegree[p]--;
            }
            return true;
        }
    };

Log in to reply
 

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