P125 上课顺序

描述#

这个题目说的是，你有 n 门课要上，课程编号从 0 到 n-1。在上某些课之前你需要先上另外一些课程，这种依赖关系可以用一个数对来表示。比如 (0,1) 数对表示在上课程 0 之前，需要先上课程 1。现在给你 n 门课以及它们之间的依赖关系，你要计算出完成这 n 门课程的一个上课顺序。如果有多个可行顺序，只要返回其中一个即可。如果无法上完所有课程，则返回一个空数组。

比如说，给你的课程数量 n 等于 5：
n = 5
课程之间的依赖关系是：
(1, 0)
(3, 0)
(3, 1)
(2, 1)
(2, 3)
(4, 2)
(4, 3)
我们只要按照 0, 1, 3, 2, 4 的顺序来上课，就可以在满足依赖关系的条件下完成这 5 门课。因此返回这个数组：
[0, 1, 3, 2, 4]
提示：上述依赖关系可以转成以下有向图
0 ---> 3 ---> 4
\    ^ \    ^
\  /   \  /
v/     v/
1 ---> 2

代码#

public class AlgoCasts {

  private boolean hasCycle(List<List<Integer>> graph, boolean[] visited,
                           boolean[] checked, List<Integer> order, int v) {
    if (visited[v]) return true;
    visited[v] = true;
    for (int i: graph.get(v))
      if (!checked[i] && hasCycle(graph, visited, checked, order, i))
        return true;
    checked[v] = true;
    order.add(v);
    visited[v] = false;
    return false;
  }

  // Time: O(V+E), Space: O(V+E)
  public int[] findOrderDFS(int n, int[][] pairs) {
    List<List<Integer>> graph = new ArrayList<>(n);
    for (int i = 0; i < n; ++i)
      graph.add(new LinkedList<>());

    for (int[] pair: pairs)
      graph.get(pair[1]).add(pair[0]);

    boolean[] checked = new boolean[n];
    boolean[] visited = new boolean[n];
    List<Integer> list = new ArrayList<>(n);
    for (int i = 0; i < n; ++i)
      if (!checked[i] && hasCycle(graph, visited, checked, list, i))
        return new int[]{};

    int[] order = new int[n];
    for (int v: list)
      order[--n] = v;
    return order;
  }

  // Time: O(V+E), Space: O(V+E)
  public int[] findOrderTopoSort(int n, int[][] pairs) {
    int[] inDegree = new int[n];
    List<List<Integer>> graph = new ArrayList<>(n);
    for (int i = 0; i < n; ++i)
      graph.add(new LinkedList<>());

    for (int[] pair: pairs) {
      graph.get(pair[1]).add(pair[0]);
      ++inDegree[pair[0]];
    }

    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < inDegree.length; ++i)
      if (inDegree[i] == 0)
        q.add(i);

    int[] order = new int[n];
    int size = 0;
    while (!q.isEmpty()) {
      int v = q.poll();
      order[size++] = v;
      for (int i: graph.get(v)) {
        --inDegree[i];
        if (inDegree[i] == 0) q.add(i);
      }
    }
    return size == n ? order : new int[]{};
  }

}