P124 课程安排

描述#

这个题目说的是，你有 n 门课要上，课程编号从 0 到 n-1。在上某些课之前你需要先上另外一些课程，这种依赖关系可以用一个数对来表示。比如 (0,1) 数对表示在上课程 0 之前，你需要先上课程 1。现在给你 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 门课。因此返回 true。
提示：上述依赖关系可以转成以下有向图
0 ---> 3 ---> 4
\    ^ \    ^
\  /   \  /
v/     v/
1 ---> 2

代码#

public class AlgoCasts {

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

  // Time: O(V+E), Space: O(V+E)
  public boolean canFinishDFS(int n, int[][] pairs) {
    if (n <= 1 || pairs == null || pairs.length == 0)
      return true;

    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];
    for (int i = 0; i < n; ++i)
      if (!checked[i] && hasCycle(graph, visited, checked, i))
        return false;
    return true;
  }

  // Time: O(V+E), Space: O(V+E)
  public boolean canFinishTopoSortAdjList(int n, int[][] pairs) {
    if (n <= 1 || pairs == null || pairs.length == 0)
      return true;

    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 count = 0;
    while (!q.isEmpty()) {
      int v = q.poll();
      ++count;
      for (int i: graph.get(v)) {
        --inDegree[i];
        if (inDegree[i] == 0) q.add(i);
      }
    }
    return count == n;
  }

}