例题目录

• 1、课程表

例题

1、课程表

题目描述：

你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]

给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？

示例 1:

输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。

算法

确定图是有向无环图（DAG），拓扑排序

• 方法一 DFS
  首先得到邻接表。
  用一个数组visited记录节点访问情况，没有被访问时为0，正在被访问为1，访问过了为-1；
  dfs时遇到1时说明有环，遇到-1表示该节点满足无环，直接返回true。

• 方法二 BFS
  数据结构：队列
  int visited
  统计所有节点的入度，如果入度为 0，则加入队列，不断弹出队列中的节点，遍历节点的相邻节点，入度减一，如果入度为0加入队列。每从队列中弹出一个节点，则visited加一，最后判断visited是否等于numCourses。

代码

// 方法一 DFS
class Solution {
    int[] visited;
    List<List<Integer>> adj;
    int numCourses;
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        this.numCourses = numCourses;
        visited = new int[numCourses];
        adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] rel : prerequisites) {
            adj.get(rel[1]).add(rel[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (visited[i] == 0 && !dfs(i)) {
                return false;
            }
        }
        return true;
    }

    private boolean dfs(int i) {
        if (visited[i] == 1) return false;
        else if (visited[i] == -1) return true;
        visited[i] = 1;
        for (int k : adj.get(i)) {
            if (!dfs(k)) {
                return false;
            }
        }
        visited[i] = -1;
        return true;
    }
}

每个节点被访问一次，并且需要建立邻接表，所以时间复杂度为O(m+n)。
空间：需要O(m+n)的邻接表，递归栈最深为O(n)，因此为O(m+n)。

// 方法二 BFS
List<List<Integer>> adj;
Queue<Integer> queue;
int[] inDegree;

public boolean canFinish(int numCourses, int[][] prerequisites) {
    adj = new ArrayList<>();
    queue = new LinkedList<>();
    inDegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) {
        adj.add(new ArrayList<>());
    }
    for (int[] ints : prerequisites) {
        adj.get(ints[1]).add(ints[0]);
        inDegree[ints[0]]++;
    }

    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) {
            queue.add(i);
        }
    }

    int visited = 0;
    while (!queue.isEmpty()) {
        visited++;
        int u = queue.poll();
        for (int v : adj.get(u)) {
            inDegree[v]--;
            if (inDegree[v] == 0) {
                queue.add(v);
            }
        }
    }
    return visited == numCourses;
}

O(m+n) O(m+n)
类似题目：210. 课程表 II
最后需要返回进修课程的顺序。
dfs每访问完一个节点，加入答案集的最后。
bfs每弹出一个节点，加入答案集的开始。