【每日一题Day322】LC210课程表 II | 拓扑排序

课程表 II【LC210】

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。

• 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

相似题目

• 思路：拓扑排序

  由于在选修课程 ai 前 必须 先选修 bi ，因此我们可以构建一条由bi 指向 ai的边，然后使用拓扑排序，优先遍历入度为0的节点，并将其加入拓扑排序数组中，如果最后数组的大小与节点个数不相同，那么证明有向图中有环存在，不可能完成所有课程

• 实现

  class Solution {
      public int[] findOrder(int numCourses, int[][] prerequisites) {
          int[] inDeg = new int[numCourses];
          List<Integer>[] g = new ArrayList[numCourses];
          Arrays.setAll(g, e -> new ArrayList<>());
          for (int[] p : prerequisites){
              int u = p[1], v = p[0];
              g[u].add(v);
              inDeg[v]++;
          }
          Deque<Integer> queue = new LinkedList<>();
          List<Integer> order = new ArrayList<>();
          for (int i = 0; i < numCourses; i++){
              if (inDeg[i] == 0){
                  queue.addLast(i);
              }
          }
          while (!queue.isEmpty()){
              int u = queue.pollFirst();
              order.add(u);
              for (int v : g[u]){
                  inDeg[v]--;
                  if (inDeg[v] == 0){
                      queue.addLast(v);
                  }
              }
          }
          return order.size() == numCourses ? order.stream().mapToInt(x -> x).toArray() : new int[]{};
  
  
  
      }
  }
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33

  • 复杂度

    • 时间复杂度：$O(E+V)$，$E$表示邻边的跳数，V为结点的个数

    • 空间复杂度：$O(V)$