Simple c++ solution using toposort


  • 3
    Q
    class Solution 
    {
    public:
        bool canFinish(int numCourses, vector<vector<int>>& prerequisites) 
        {
            vector<int> G[numCourses];
            int de[numCourses]{};
            queue<int> Q;
            
            for (auto rel : prerequisites)
            {
                G[rel[1]].push_back(rel[0]);
                de[rel[0]] ++;
            }
            
            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();
                cnt --;
                for (int u : G[cur])
                {
                    de[u] --;
                    if (de[u] == 0)
                        Q.push(u);
                }
            }
            
            return cnt == 0;
        }
    };
    

    array "de" means input degree;
    and the queue Q contains the nodes ready to be removed (input degree equals to zero)
    if all of the nodes were removed after the process, there is no cycle.


Log in to reply
 

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