topological sorting 12ms beats 100%


  • 0
    M

    class Solution {
    public:
    bool canFinish(int num, vector<pair<int, int>>& pre) {

        int n = pre.size();
        if(num == 0) return false;
        queue<int> q;
        int counter = 0;
        vector<int> mp[num],G[num];
        int ind[num] = {0,};
        
        for(int i=0;i<n;i++){
            mp[pre[i].first].push_back(pre[i].second);
            G[pre[i].second].push_back(pre[i].first);
        }
        
        for(int i=0;i<num;i++) ind[i] = mp[i].size();
        
        for(int i=0;i<num;i++){
            
            if(ind[i] == 0) q.push(i);
        }
        
        while(!q.empty()){
            
            int v = q.front();
            counter++;
            for(int i=0;i<G[v].size();i++){
                
                if(--ind[G[v][i]] == 0) q.push(G[v][i]);
            }
            q.pop();
        }
        if(counter != num) return false;
        return true;
    
    }
    

    };


Log in to reply
 

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