message: Update course-schedule.cpp
diff: // Time: O(|V| + |E|)
  // Space: O(|E|)
  -// Topological sort solution.
  +// dfs solution
  class Solution {
  public:
  bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
  - // Store courses with in-degree zero.
  - queue<int> zeroInDegree;
  -
  - // in-degree, out-degree
  - unordered_map<int, unordered_set<int>> inDegree;
  - unordered_map<int, unordered_set<int>> outDegree;
  - for (int i = 0; i < prerequisites.size(); ++i) {
  - inDegree[prerequisites[i][0]].insert(prerequisites[i][1]);
  - outDegree[prerequisites[i][1]].insert(prerequisites[i][0]);
  + unordered_map<int, unordered_set<int>> in_degree, out_degree;
  + for (const auto& p : prerequisites) {
  + in_degree[p[0]].emplace(p[1]);
  + out_degree[p[1]].emplace(p[0]);
  }
  -
  - // Put all the courses with in-degree zero into queue.
  + queue<int> q;
  for (int i = 0; i < numCourses; ++i) {
  - if(inDegree.find(i) == inDegree.end()) {
  - zeroInDegree.push(i);
  + if (!in_degree.count(i)) {
  + q.emplace(i);
  }
  }
  -
  - // V+E
  - while(!zeroInDegree.empty()) {
  - // Take the course which prerequisites are all taken.
  - int prerequisite = zeroInDegree.front();
  - zeroInDegree.pop();
  - for (const auto & course: outDegree[prerequisite]) {
  - // Update info of all the courses with the taken prerequisite.
  - inDegree[course].erase(prerequisite);
  - // If all the prerequisites are taken, add the course to the queue.
  - if (inDegree[course].empty()) {
  - zeroInDegree.push(course);
  - }
  - }
  - // Mark the course as taken.
  - outDegree.erase(prerequisite);
  + while (!q.empty()) {
  + const auto node = q.front(); q.pop();
  + for (const auto& i : out_degree[node]) {
  + in_degree[i].erase(node);
  + if (in_degree[i].empty()) {
  + q.emplace(i);
  + in_degree.erase(i);
  }
  -
  - // All of the courses have been taken.
  - if (!outDegree.empty()) {
  - return false;
  }
  + out_degree.erase(node);
  + }
  + return in_degree.empty() && out_degree.empty();
  + }
  +};
  - return true;
  +// Time: O(|V| + |E|)
  +// Space: O(|E|)
  +// bfs solution
  +class Solution2 {
  +public:
  + bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
  + unordered_map<int, unordered_set<int>> in_degree, out_degree;
  + for (const auto& p : prerequisites) {
  + in_degree[p[0]].emplace(p[1]);
  + out_degree[p[1]].emplace(p[0]);
  + }
  + vector<int> stk;
  + for (int i = 0; i < numCourses; ++i) {
  + if (!in_degree.count(i)) {
  + stk.emplace_back(i);
  + }
  + }
  + while (!stk.empty()) {
  + const auto node = stk.back(); stk.pop_back();
  + for (const auto& i : out_degree[node]) {
  + in_degree[i].erase(node);
  + if (in_degree[i].empty()) {
  + stk.emplace_back(i);
  + in_degree.erase(i);
  + }
  + }
  + out_degree.erase(node);
  + }
  + return in_degree.empty() && out_degree.empty();
  }
  };
  