描述

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

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

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

示例

示例 1:

  1. 输入：numCourses = 2, prerequisites = [[1,0]]
  2. 输出：[0,1]
  3. 解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

  1. 输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
  2. 输出：[0,2,1,3]
  3. 解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
  4. 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3:

  1. 输入：numCourses = 1, prerequisites = []
  2. 输出：[0]

提示

  • 1 <= numCourses <= 2000
  • 0 <= prerequisites.length <= numCourses * (numCourses - 1)
  • prerequisites[i].length == 2
  • 0 <= ai, bi < numCourses
  • ai != bi
  • 所有[ai, bi] 匹配 互不相同


解题思路

官方题解讲的很好，直接看这里： 官方题解

代码

  1. class Solution {
  2.     // 存储有向图
  3.     List<List<Integer>> edges;
  4.     // 存储每个节点的入度
  5.     int[] indeg;
  6.     // 存储答案
  7.     int[] result;
  8.     // 答案下标
  9.     int index;
  11.     public int[] findOrder(int numCourses, int[][] prerequisites) {
  12.         edges = new ArrayList<List<Integer>>();
  13.         for (int i = 0; i < numCourses; ++i) {
  14.             edges.add(new ArrayList<Integer>());
  15.         }
  16.         indeg = new int[numCourses];
  17.         result = new int[numCourses];
  18.         index = 0;
  19.         for (int[] info : prerequisites) {
  20.             edges.get(info[1]).add(info[0]);
  21.             ++indeg[info[0]];
  22.         }
  24.         Queue<Integer> queue = new LinkedList<Integer>();
  25.         // 将所有入度为 0 的节点放入队列中
  26.         for (int i = 0; i < numCourses; ++i) {
  27.             if (indeg[i] == 0) {
  28.                 queue.offer(i);
  29.             }
  30.         }
  32.         while (!queue.isEmpty()) {
  33.             // 从队首取出一个节点
  34.             int u = queue.poll();
  35.             // 放入答案中
  36.             result[index++] = u;
  37.             for (int v: edges.get(u)) {
  38.                 --indeg[v];
  39.                 // 如果相邻节点 v 的入度为 0，就可以选 v 对应的课程了
  40.                 if (indeg[v] == 0) {
  41.                     queue.offer(v);
  42.                 }
  43.             }
  44.         }
  46.         if (index != numCourses) {
  47.             return new int[0];
  48.         }
  49.         return result;
  50.     }
  51. }