LeetCode 207：课程表（拓扑排序判断是否成环）

LeetCode 207

题目：

思路：

看到依赖问题，首先想到把问题转换为有向图 ！

1. 利用条件构建图，课程即顶点，几个节点就有几个顶点，以个数建立List[ ]数组表示图，数组的索引就是顶点的值，数组的每个元素都是顶点对应的邻接表；
   用先学习的课程pre指向后学习的课程follow来表示有向图的顺序
2. main中用第一个for遍历图的每个顶点，对顶点的邻接表使用dfs
3. 在dfs中用第二个for遍历该顶点的邻接表
   当onpath为真则标记isCycle为true
   注意for结束后要还原 onpath=false

注意：
为便于记忆，当onpath[s]=true 和 marked[s]=true 都直接return

Java实现：

class Solution {
    
    boolean[] marked;
    boolean[] onPath;
    boolean isCycle=false;

    public boolean canFinish(int numCourses, int[][] prerequisites) {
    
        // 不可能完成： 即存在循环依赖，互相为前提, 就不能完成课程
        //构建图
        List<Integer>[] graph=buildGraph(numCourses,prerequisites);
        //初始化
        marked=new boolean[numCourses];
        onPath=new boolean[numCourses];
    
        //用dfs遍历每个顶点
        for(int i=0;i<numCourses;i++){
    
            dfs(graph,i);           
        }
        return !isCycle;//不成环即可以完成学习
    }
    	
        List<Integer>[] buildGraph(int numCourses,int[][]prerequisites){
    
            List<Integer>[] graph=new List[numCourses];//graph元素是数组！
            //初始化每个元素：new一个List作为邻接表
            for(int i=0;i<numCourses;i++){
    
                graph[i]=new LinkedList<>();
            }
            //添加有向边
            for(int[] k:prerequisites){
    
                int pre=k[1];
                int follow=k[0];
                graph[pre].add(follow); // graph的索引对应顶点的值，
            }
            return graph;
        }
    }
    
        void dfs(List<Integer>[] graph,int s){
    
            //终止条件
            if(onPath[s]==true){
    
                isCycle=true;
                return;
            }
            if(marked[s]==true){
    
                return;
            }
            marked[s]=true;//标记当前s
            onPath[s]=true;//标记onpath
            //遍历邻接表
            for(int k:graph[s]){
    
                    dfs(graph,k);
            }
            onPath[s]=false;//onpath还原
        }