LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 与 #207 思路相同，返回一个拓扑序列即可

class Solution {
 public:
  vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    unordered_map<int, vector<int>> m;  // 邻接表（节点及其所有后继节点）
    vector<int> indegree(numCourses);  // 节点的入度（以该点为后继节点的边数）
    for (auto& x : prerequisites) {
      m[x[1]].emplace_back(x[0]);  // 题目中 x[1] 是前驱节点，x[1]->x[0]
      ++indegree[x[0]];            // x[0] 入度加 1
    }
    queue<int> q;
    for (int i = 0; i < size(indegree); ++i) {
      if (!indegree[i]) {
        q.emplace(i);  // 把入度为 0 的点添加到队列中
      }
    }
    vector<int> res;
    while (!empty(q)) {
      int n = q.front();  // 入度为 0 的点
      q.pop();            // 取出该点
      res.emplace_back(n);
      for (auto& x : m[n]) {  // 遍历该点所有后继节点
        --indegree[x];  // 因为删除了当前节点，后继节点入度减一
        if (!indegree[x]) {
          q.emplace(x);  // 如果后继节点入度为 0 则推入队列中
        }
      }
    }
    if (size(res) < numCourses) {
      return {};
    }
    return res;  // 遍历了所有点则说明是有向无环图，res 是拓扑序列
  }
};