O(m + n) C++ topological sort solution via BFS


  • 0
    A

    O(m + n) time and space

    topological sort via BFS
    according to hints. detect cycle in directed graph. hint is Topological sort via BFS.

    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<int> inDegrees(numCourses, 0);
            vector<vector<int>> graph(numCourses);
            for (auto edge : prerequisites) {
                graph[edge.second].push_back(edge.first);
                ++inDegrees[edge.first];
            }
            
            queue<int> q;
            for (int i = 0; i < numCourses; ++i) {
                if (!inDegrees[i])
                    q.push(i);
            }
            
            while (!q.empty()) {
                int node = q.front();
                q.pop();
                
                for (int next : graph[node]) {
                    --inDegrees[next];
                    if (!inDegrees[next])
                        q.push(next);
                }
                
                graph[node].clear();
            }
            
            for (auto nextNodes : graph) {
                if (!nextNodes.empty())
                    return false;
            }
            
            return true;
        }
    };
    

Log in to reply
 

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