LeetCode 210：课程表 II （拓扑排序）

LeetCode 210

题目：

思路：

拓扑排序理论
仅在判断是否成环基础上增加了一个list用于记录

注意：

1. 递归到头才开始记录，所以是后续遍历
2. Queue和Stack都有size()方法，继承于Collection和Vector
3. 终止条件在前，onPath在marked之前！

class Solution {
    
    boolean isCycle=false;
    List<Integer> list=new ArrayList<>();
    boolean[] marked;
    boolean[] onPath;
    
    public int[] findOrder(int numCourses, int[][] prerequisites) {
    
        List<Integer>[] graph=buildGraph(prerequisites,numCourses);
        marked=new boolean[numCourses];
        onPath=new boolean[numCourses];
        for(int i=0;i<numCourses;i++){
     //遍历顶点
            dfs(graph,i);
        }
        if(isCycle){
    
            return new int[]{
    };
        }
        int n=list.size();
        int[] r=new int[n];
        Collections.reverse(list);
        for(int i=0;i<n;i++){
    
            r[i]=list.get(i);
        }
        return r;
    }

    List<Integer>[] buildGraph(int[][] prerequisites,int numCourses){
    
        List<Integer>[] graph=new List[numCourses];
        for(int i=0;i<numCourses;i++){
    
            graph[i]=new LinkedList<Integer>();
        }
        for(int[] k:prerequisites){
    
            int pre=k[1];
            int follow=k[0];
            graph[pre].add(follow);
        }
        return graph;
    }   

    void dfs(List<Integer>[] graph,int s){
    
        //终止条件, onPath在marked 之前 ！
        if(onPath[s]){
    
            isCycle=true;
            return;
        }
        if(marked[s]){
    
            return ;
        }
        marked[s]=true;
        onPath[s]=true;
        for(int k:graph[s]){
     //遍历邻接表
            dfs(graph,k);
        }
        list.add(s); // 后续遍历 ！
        onPath[s]=false;    
    }
}

或者用栈来记录：

		int n=stack.size();
        int[] r=new int[n];
        for(int i=0;i<n;i++){
    
            r[i]=stack.pop();
        }
        return r;