13ms BFS solution with detailed comments


  • 0
    L
    class Solution {
    public:
        bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
            vector<unordered_set<int>> graph = make_graph(numCourses, prerequisites);
            vector<int> indegree = get_indegree(numCourses, graph);
            queue<int> zeros; // zeros used to store all the course number that's with zero indegree
            for (int i = 0; i < indegree.size(); i++) {
                if (indegree[i] == 0) {
                    zeros.push(i);
                }
            }
        
            vector<int> ans;
            // use BFS to traverse from the source to the end
            while (!zeros.empty()) {
                int tmp = zeros.front();
                zeros.pop();
                ans.push_back(tmp);
                for (int course: graph[tmp]) {
                    --indegree[course];
                    if (!indegree[course]) {
                        zeros.push(course);
                    }
                }
            }
            if (ans.size() != numCourses) {
                return false;
            }
            return true;
        }
        
        vector<unordered_set<int>> make_graph(int numCourses, vector<pair<int, int>> &prerequisites) {
            vector<unordered_set<int>> graph(numCourses);
            
            for (auto item : prerequisites) {
                graph[item.second].insert(item.first);
            }
            return graph;
        }
        
        vector<int> get_indegree(int numCourses, vector<unordered_set<int>> &graph) {
            vector<int> indegree(numCourses, 0);
            
            for (int i = 0; i < graph.size(); i++) {
                for (int course : graph[i]) {
                    indegree[course]++;
                }
            }
            return indegree;
        }
    };
    

Log in to reply
 

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