Accepted 264ms c++ solution using topological sort and queue.

• Accepted 264ms c++ solution using topological sort for Course Schedule.

``````class Solution {
public:
bool canFinish(int numCourses, std::vector<std::pair<int, int> > &prerequisites) {
std::vector<std::unordered_set<int> > need(numCourses);
for (std::size_t i = 0; i != prerequisites.size(); ++i)
need[prerequisites[i].second].insert(prerequisites[i].first);
std::vector<int> indegree(numCourses);
for (int i = 0; i != numCourses; ++i)
for(auto it = need[i].begin(); it != need[i].end(); ++it)
++indegree[*it];
std::queue<int> zeros;
for (int i = 0; i != numCourses; ++i)
if (indegree[i] == 0)
zeros.push(i);
while (!zeros.empty()) {
int seq = zeros.front();
zeros.pop();
for (auto it = need[seq].begin(); it != need[seq].end(); ++it)
if (--indegree[*it] == 0)
zeros.push(*it);
--numCourses;
}
return numCourses == 0;
}
};
``````

Accepted 500ms c++ solution using topological sort for Course Schedule II.

``````class Solution {
public:
std::vector<int> findOrder(int numCourses, std::vector<std::pair<int, int> >& prerequisites) {
std::vector<std::unordered_set<int> > need(numCourses);
for (std::size_t i = 0; i != prerequisites.size(); ++i)
need[prerequisites[i].second].insert(prerequisites[i].first);
std::vector<int> indegree(numCourses);
for (int i = 0; i != numCourses; ++i)
for(auto it = need[i].begin(); it != need[i].end(); ++it)
++indegree[*it];
std::queue<int> zeros;
for (int i = 0; i != numCourses; ++i)
if (indegree[i] == 0)
zeros.push(i);
std::vector<int> res;
while (!zeros.empty()) {
int seq = zeros.front();
zeros.pop();
res.push_back(seq);
for (auto it = need[seq].begin(); it != need[seq].end(); ++it)
if (--indegree[*it] == 0)
zeros.push(*it);
}
return res.size() == numCourses ? res : std::vector<int>();
}
};
``````

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