Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
669 B
2
Indexable
Never
class Solution {
public:
    bool canFinish(int num, vector<vector<int>>& pre) {
        vector<vector<int>> graph(num); //graph is actually a adjlist
        vector<int>in(num,0);
        for(auto it:pre){
            graph[it[1]].push_back(it[0]);
            in[it[0]]++;
        }
        queue<int> q;
        for(int i=0;i<num;i++){
            if(in[i]==0) q.push(i);
        }
        while(!q.empty()){
            int f=q.front();
            q.pop();
            num--;
            for(auto nbr:graph[f]){
                in[nbr]--;
                if(in[nbr]==0) q.push(nbr);
            }
        }
        return (num==0);
    }
};