C++ code. implementation of Topology Sort by using queue. Defeat 96.97%


  • 0
    Y
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            int* indegree = (int*)malloc(sizeof(int) * numCourses);
            vector<vector<int>> graph(numCourses);
            memset(indegree, 0, sizeof(int) * numCourses);
            for (auto& u : prerequisites) { indegree[u.second] += 1; graph[u.first].push_back(u.second); }
            std::queue<int> indeg0;
            for (int i = 0; i < numCourses; ++i) {
                if (indegree[i] == 0) indeg0.push(i);
            }
            if (indeg0.empty() && numCourses) return false;
            int count = 0;
            int node = 0;
            while (!indeg0.empty()) {
                ++count;
                node = indeg0.front();
                indeg0.pop();
                for (auto& p : graph[node]) {
                    --indegree[p];
                    if (indegree[p] == 0) indeg0.push(p);
                }
            }
            if (count != numCourses) return false;
            return true;
        }
    

Log in to reply
 

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