207. 课程表
难度中等534收藏分享切换为英文关注反馈
你这个学期必须选修 numCourse 门课程，记为 0 到 numCourse-1 。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们：[0,1]
给定课程总量以及它们的先决条件，请你判断是否可能完成所有课程的学习？
示例 1:
输入: 2, [[1,0]] 输出: true 解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]] 输出: false 解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成?课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
提示：
- 输入的先决条件是由 边缘列表 表示的图形，而不是 邻接矩阵 。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
1 <= numCourses <= 10^5
解题思路：
1、学习课程看做一点n1，先学课程看做一点n2，先学课程与学习课程之间的联系看做由n2指向n1的有向边；遍历所有的课程节点，以某门课程c1开始，搜索所有与c1相关的节点，判断课程节点之间是否存在相互依赖，即是否有环路出现，有环路存在则不可能完成，没有环路存在，则可以完成。
2、判断是否有环路出现，可能通过一个数组来记录当前节点的状态，未访问的节点状态记作0，正在访问的节点记作1，已经访问完成的节点状态记作2；若在搜索过程，出现节点状态为1的情况，则证明有环路存在。
import java.util.ArrayList;
import java.util.List;public class CanFinish {//访问数组private static int[] visited ;//课程集合private static List<List<Integer>> courseList = new ArrayList<>();//是否可行private static boolean flag = true;public static boolean canFinish(int numCourses, int[][] prerequisites) {visited = new int[numCourses];for(int i=0;i<numCourses;i++){courseList.add(new ArrayList<>());}for(int j=0;j<prerequisites.length;j++){courseList.get(prerequisites[j][1]).add(prerequisites[j][0]);}for(int k=0;k<courseList.size();k++){if(visited[k] == 0 && flag){dfs(k);}}return flag;}public static void dfs(int courseNum){//正在搜索中visited[courseNum] = 1;for(int id:courseList.get(courseNum)){if(visited[id] == 0){dfs(id);}else if(visited[id] == 1){flag = false;return;}}visited[courseNum] = -1;}public static void main(String[] args){int numCourses = 2;int[][] prerequisites = new int[][]{{1,0},{0,1}};System.out.println(canFinish(numCourses,prerequisites));}}