一、题目描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[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 。这是不可能的。
提示：
1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同
二、思路讲解
这是一道经典的拓扑排序问题，课程能不能修完 == 有向图中是否存在环，有向图中，一个节点的入度为他的先修课程。
2.1 方法一：广度优先搜索bfs
思路如下：通过bfs进行拓扑排序。利用一个队列，将入度数为0的节点加入到队列中（这些课程没有先修课程，可以访问），然后将队列中的节点依次出队，每出队一个节点，就相当于访问了这个节点（修了这门课程），就要将它在有向图中“删除”，即将它所有的出度的入度数都-1，然后将这时可能有些课程的入度数为0了，那这也是可以修的课程，也将他放入队列中。当队列为空时，拓扑排序完成，如果所有节点都访问到了，说明有向图中没有环；反之，有环。
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { //记录入度数 int []indegrees = new int[numCourses]; //出度表 List<List<Integer>> edegree = new ArrayList<>(); for(int i=0; i<numCourses; i++) { edegree.add(new ArrayList<Integer>()); } //统计每个节点的出度节点 和 入度数 for(int i=0; i<prerequisites.length; i++) { edegree.get(prerequisites[i][1]).add(prerequisites[i][0]); indegrees[prerequisites[i][0]]++; } //bfs Queue<Integer> queue = new LinkedList<>(); for(int i=0; i<numCourses; i++) { if(indegrees[i] == 0) { queue.add(i); } } int visited = 0; //访问节点的数量，如果和节点总数一致，说明每个节点都访问到了，有向图中不存在环 while(!queue.isEmpty()) { visited++; int node = queue.poll(); //把该节点的所有出度的入度数都-1，相当于把这个节点从有向图中删除 for(int ede : edegree.get(node)) { indegrees[ede]--; //把入度数为0的节点放到队列中，这些节点是可以访问的 if(indegrees[ede] == 0) { queue.add(ede); } } } return visited==numCourses; } }
时间复杂度： O(M + N) M为课程数，N为先修课程的要求数
空间复杂度： O(M + N)
2.2 深度优先搜索dfs
跟bfs从入度思考相比，dfs从出度思考，更像是一种逆向思维。
思路：深度遍历判断有向图是否存在环。用visit数组记录节点的访问状态（1：当前节点正在访问； 0：未被访问； -1：被其他节点访问过）。如果当前节点的状态为-1，说明已经被其他节点访问过，已经被从有向图中“删除了”，无需考虑；而状态为1，说明是正在被访问的，则说明走了回头路，即存在环。
class Solution { public boolean canFinish(int numCourses, int[][] prerequisites) { //记录每个节点的访问情况 1：当前节点正在访问； 0：未被访问； -1：被其他节点访问过 int []visit = new int[numCourses]; //出度表 List<List<Integer>> edegree = new ArrayList<>(); for(int i=0; i<numCourses; i++) { edegree.add(new ArrayList<Integer>()); } //统计每个节点的出度节点 for(int i=0; i<prerequisites.length; i++) { edegree.get(prerequisites[i][1]).add(prerequisites[i][0]); } for(int i=0; i<numCourses; i++) { if(!dfs(edegree, visit, i)) { return false; } } return true; } boolean dfs(List<List<Integer>> edegree, int []visit, int i) { //如果已经被其他节点访问过，说明不需要再访问了 if(visit[i] == -1) { return true; } //正在被当前节点访问，说明走了回头路，即存在环 if(visit[i] == 1) { return false; } visit[i] = 1; //向下访问，每个出度都要走到 for(int ede : edegree.get(i)) { if(!dfs(edegree, visit, ede)) { return false; } } visit[i] = -1; return true; } }
可以把邻接表和访问状态数组设置为公共变量，减少递归传参对性能的损耗：
class Solution { int []visit; List<List<Integer>> edegree; public boolean canFinish(int numCourses, int[][] prerequisites) { visit = new int[numCourses]; edegree = new ArrayList<>(); for(int i=0; i<numCourses; i++) { edegree.add(new ArrayList<Integer>()); } //统计每个节点的出度节点 for(int i=0; i<prerequisites.length; i++) { edegree.get(prerequisites[i][1]).add(prerequisites[i][0]); } for(int i=0; i<numCourses; i++) { if(!dfs(i)) { return false; } } return true; } boolean dfs(int i) { if(visit[i] == -1) { return true; } if(visit[i] == 1) { return false; } visit[i] = 1; for(int ede : edegree.get(i)) { if(!dfs(ede)) { return false; } } visit[i] = -1; return true; } }
时间复杂度： O(M + N) M为课程数，N为先修课程的要求数
空间复杂度： O(M + N)
