13ms BFS solution with detailed comments

• ``````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;
}
};
``````

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