207. 课程表-白红宇

207. 课程表

阅读量：121 次

发布时间：2019-02-26

本文共 5206 字，大约阅读时间需要 17 分钟。

你这个学期必须选修 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来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/course-schedule著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

//题解是深度优先遍历class Solution {       private  List
   
    
     > edges;    private  byte[] visited;//0:为搜索;1:搜索完成；2：搜索中    private  Stack
     
       stack;    private  boolean ans = true;    public boolean canFinish(int numCourses, int[][] prerequisites) {           edges = new ArrayList<>();        stack = new Stack<>();        visited = new byte[numCourses];        //初始化        for (int i = 0; i < numCourses; i++) {               edges.add(new LinkedList<>());        }        for (int[] prerequisite : prerequisites) {               edges.get(prerequisite[1]).add(prerequisite[0]);        }        for (int i = 0; i < edges.size(); i++) {               if (visited[i] == 0) {                   dfs(i);            }        }        // System.out.println(Arrays.toString(edges.toArray()));        // System.out.print("[");        // for (byte b : visited) {           //     System.out.print(b + ",");        // }        // System.out.print("]\n");        return ans;    }    private  void dfs(int i) {           visited[i] = 2;//设置该节点正在搜索中        List
      
        integers = edges.get(i);        if (integers.size() == 0) {               // System.out.print(i + "->");            visited[i] = 1;//该节点搜索完成            return;        }        for (Integer integer : integers) {               if (visited[integer] == 0) {                   dfs(integer);            } else if (visited[integer] == 2) {                   ans = false;                return;            }        }        visited[i] = 1;//该节点搜索完成        // System.out.print(i + "->");    }}

e.g.总共有7门课程，每门课程修完后可解锁的课程图如下		A->C;A->F;A->E;    0->{2,4,5}		B->A;B->C;         1->{0,2}		C                  2->{}       		D->F               3->{5}		E				   4->{}		F->E;F->G          5->{4,6}		G				   6->{}1.我一开始不完善的解法思路	(1).获取课程的图表示，即上完本课程可接下来上什么课程	(2).设置一个visited数组用于保存每一个课程的状态，0->未学习；1->学习完成;2->学习中	(3).依次遍历每一个课程，从0->6,若该课程已经学习过了，就直接跳过该课程	(4).每遍历一个课程，设置该课程为正在学习中，然后获取该课程对应的解锁课程，再依次遍历每一个解锁的课程	(5).若当前课程没有可解锁的课程，说明当前课程已经学完了，设置当前课程状态为1；若当前课程可解锁的课程全部都解锁完成了，设置当前课程为1，表示当前课程也全部都学完了。	(6).若最终程序陷入了死循环，抛出了栈溢出错误，说明图中有环；		若最终程序正常结束，说明该题有解；2.我后来较完善的思路	(1).获取课程的图表示，即上完本课程可接下来上什么课程	(2).设置一个visited数组用于保存每一个课程的状态，0->未学习；1->学习完成;2->学习中	(3).依次遍历每一个课程，从0->6,若该课程已经学习过了，就直接跳过该课程	(4).每遍历一个课程，设置该课程为正在学习中，然后获取该课程对应的解锁课程，再依次遍历每一个解锁的课程	(PS:若在遍历过程中发现居然还有正在学习的过程，说明图中有环，直接退出程序，返回false)	(5).若当前课程没有可解锁的课程，说明当前课程已经学完了，设置当前课程状态为1；若当前课程可解锁的课程全部都解锁完成了，设置当前课程为1，表示当前课程也全部都学完了。	(6).若最终程序陷入了死循环，抛出了栈溢出错误，说明图中有环；若最终程序正常结束，说明该题有解；3.具体思路	正例：		A->C;A->F;A->E;    0->{2,4,5}		B->A;B->C;         1->{0,2}		C                  2->{}       		D->F               3->{5}		E				   4->{}		F->E;F->G          5->{4,6}		G				   6->{}		1.构造图，请直接阅读上述源码		2.依次遍历每一个节点，此时visited=[0,0,0,0,0,0,0]			1.0.i=0;dfs(0) ,				 visited[0] == 0;//因此进入该课程的回溯dfs(0);				 visited[0] = 2;//设置该课程状态为正在学习中,此时visited=[2,0,0,0,0,0,0]				 	List
   
    integers = edges.get(0);//integers = 3,在依次遍历这3个课程   0->{2,4,5}						visited[2] ==0//课程2尚未学习过，回溯该课程			1.1	    i=2;dfs(2);						visited[2] = 2;//visited=[2,0,2,0,0,0,0]						List
    
     integers = edges.get(2);//2->{},可解锁课程为空，说明该课程可学习完成，置1 return返回，visited=[2,0,1,0,0,0,0]；			1.2	    i=4;dfs(4)						visited[4] = 2;//[2,0,1,0,2,0,0]；						List
     
      integers = edges.get(4);//4->{},visited=[2,0,1,0,1,0,0]；		     1.3	 i=5;dfs(5);						visited[5] = 2;//visited=[2,0,1,0,1,2,0]；						List
      
       integers = edges.get(5);//5->{4,6};				1.3.1		dfs(4);//课程4已经学习过了				1.3.2.	    dfs(6);//					visited[6]=2;//visited=[2,0,1,0,1,2,2]；					List
       
        integers = edges.get(6);//6->{},visited=[2,0,1,0,1,2,1]；						//因为课程5可解锁的所有课程都已经学过了	5->{4,6};，因此visited[5]  =1;visited=[2,0,1,0,1,1,1]；					//因为课程0可解锁的所有课程都已经学过了0->{2,4,5}，因此 visited[0] = 1; visited=[1,0,1,0,1,1,1]；									2.0.i=1;dfs(1)							visited[1] ==0;//该课程未被学习过,进入回溯				visted[1] = 2;//visited=[1,2,1,0,1,1,1]；			    List
        
         integers = edges.get(1);//1->{0,2} dfs(0);//课程0已经学习过了，跳过 dfs(2);//课程2已经学习过了，跳过 //由于课程1解锁的课程都已经修过了，因此课程1自动修完，此时 visited=[1,1,1,0,1,1,1] 3.0.i=2;dfs(2);//已经修过了，跳过 4.0.i=3;dfs(3); visited[3] ==0; visited[3] = 2；//此时visited=[1,1,1,2,1,1,1] List
         
          integers = edges.get(3);//3->{5} dfs(5);//该课程已经学习过了，return; //由于课程3可解锁的课程均已修完，故课程3默认修完,此时visited=[1,1,1,1,1,1,1] 5.0.i=4;dfs(4);//该课程已经修完 6.0;i=5;dfs(5)；该课程已经修完 7.0;i=6;dfs(6);该课程已经修完//该图无环，故可修完所有的课程 反例： A->{B} 0->{1} B->{C} 1->{2} C->{D} 2->{0}1.构造图，参考源码2.依次遍历每一个节点，visited = [0,0,0] 1.0.i=0,dfs(0) visited[0] = 2;//visited = [2,0,0] List
          
           integers = edges.get(0)//0->{1}; dfs(1); visited[1] = 2;//visited = [2,2,0] List
           
            integers = edges.get(0)//1->{2}; dfs(2); visited[2] = 2;//visited = [2,2,2] List
            
             integers = edges.get(2)//2->{0}; //此时可发现，陷入了无限循环 dfs(0); 此时判断发现visited[0]==2;//因此可知道图中有环，故直接退出程序，返回false;