My C++ code O(|V|+|E|) - small explanations


  • 5
    R
    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& pre) {
                // build the graph and compute in_degrees
                vector<int>inDegree(numCourses, 0);
                vector<vector<int>> neighbours(numCourses);
                for(int i=0; i<pre.size(); ++i){
                    neighbours[pre[i].second].push_back(pre[i].first);
                    inDegree[pre[i].first]++;
                }
                // find all in_degree==0, and mark them as visited(set inDegree to -1)
                queue<int>inDegree0;
                int count=0;
                for(int i=0; i<numCourses; ++i){
                    if(!inDegree[i]){
                        inDegree0.push(i);
                        inDegree[i]=-1;
                        count++;
                    }
                }
                // pop a node from queue, decrease the degree of the neighbours and push the degree==0    
                while(!inDegree0.empty()){
                    int cur=inDegree0.front(); inDegree0.pop();
                    for(int i=0; i<neighbours[cur].size(); ++i) {
                        inDegree[neighbours[cur][i]]--;
                        if(inDegree[neighbours[cur][i]]==0){
                            count++;
                            inDegree0.push(neighbours[cur][i]);
                            inDegree[neighbours[cur][i]]=-1;
                        }
                    }
                }
                return (count==numCourses);
        }
    };

Log in to reply
 

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