Clean C++ solution


  • 0
    X

    class Solution {
    public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
    vector<int> degree = compute(numCourses, prerequisites);
    queue<int> q;
    for (int i = 0; i < degree.size(); i++) {
    if (degree[i] == 0) q.push(i);
    }

            int count = 0;
            while (!q.empty()) {
                    int next = q.front();
                    count++;
                    q.pop();
                    for (pair<int, int> p : prerequisites) {
                            if (p.second == next) {
                                    if(--degree[p.first] == 0) q.push(p.first);
                            }
                    }
            }
            return count == numCourses;
    }
    
    vector<int> compute(int n, vector<pair<int, int>>& pre) {
            vector<int> degree(n, 0);
            for (pair<int, int> p : pre) {
                    degree[p.first]++;
            }
            return degree;
    }
    

    };


Log in to reply
 

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