#yyds干货盘点# LeetCode程序员面试金典：课程表

1.简述：

这学期你必须选修课 numCourses 课程记录为0到numCourseses - 1 。

在选修某些课程之前，你需要先修一些课程。 先修课程按数组prequisitesestes 给出，包括prerequisiteses[i] = [ai, bi] ，说如果你想学习ai课程， 则 必须 先学习课程 bi 。

例如，对[0， 1] 说：想学习课程 0 ，你需要先完成课程 1 。

请判断是否有可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

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

输出：true

解释:共有 2 课程。学习课程 1 在此之前，你需要完成课程 0 。这是可能的。

示例 2：

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

输出：false

解释:共有 2 课程。学习课程 1 在此之前，你需要先完成课程 0 ；并且学习课程 0 在此之前，你还应该先完成课程 1 。不可能。

2.实现代码：

class Solution {    List<List<Integer>> edges;    int[] visited;    boolean valid = true;    public boolean canFinish(int numCourses, int[][] prerequisites) {        edges = new ArrayList<List<Integer>>();        for (int i = 0; i < numCourses; ++i) {            edges.add(new ArrayList<Integer>());        }        visited = new int[numCourses];        for (int[] info : prerequisites) {            edges.get(info[1]).add(info[0]);        }        for (int i = 0; i < numCourses && valid; ++i) {            if (visited[i] == 0) {                dfs(i);            }        }        return valid;    }    public void dfs(int u) {        visited[u] = 1;        for (int v: edges.get(u)) {            if (visited[v] == 0) {                dfs(v);                if (!valid) {                    return;                }            } else if (visited[v] == 1) {                valid = false;                return;            }        }        visited[u] = 2;    }}