C++ solution for Course Schedule


  • 0
    G
    class Solution{
    public:
        bool canFinish(int num,vector<pair<int,int>> vec){
            if(num==0)return true;
            vector<vector<int>> pre(num);
            
            vector<int> degree(num,0);
            for(int i=0;i<vec.size();i++){
                // pre[vec[i].first].push_back(vec[i].second);
                pre[vec[i].second].push_back(vec[i].first);
                degree[vec[i].first]++;
            }
            queue<int> qq;
            int count=0;
            for(int i=0;i<num;i++)
                if(degree[i]==0){count++;qq.push(i);}
            if(qq.empty())return false;
            while(!qq.empty()){
                int node=qq.front();//
                qq.pop();
                for(int i=0;i<pre[node].size();i++)
                    if(--degree[pre[node][i]]==0){count++;qq.push(pre[node][i]);}
            }
            if(count==num)return true;
            return false;
        }
    };

Log in to reply
 

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