My Simple C++ Topological sort solution


  • 0
    N
    vector<int> findOrder(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> G[numCourses];
        int de[numCourses]{};
        queue<int> Q;
        vector<int> res;
        for (auto rel : prerequisites)
        {
            G[rel.second].push_back(rel.first);
            de[rel.first] ++;
        }
    
        for (int i = 0; i < numCourses; ++ i)
            if (de[i] == 0)
                Q.push(i);
    
        int cnt(numCourses);
    
        while (!Q.empty())
        {
            int cur = Q.front();
             Q.pop();
             res.push_back(cur);
            cnt --;
            for (int u : G[cur])
            {
                de[u] --;
                if (de[u] == 0)
                    Q.push(u);
            }
        }
    
        if(cnt==0)
            return res;
        else{
            res.resize(0);
            return res;
        }       
           
    }

Log in to reply
 

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