[数据结构与算法]拓扑排序算法leetcode.210

boolean[] mark;//之前已经遍历的节点
    boolean[] on;//本此路径上的节点
    boolean flag=false;//是否有环
    int n;//顶点数量
    int[] ans;//结果，模拟栈
    int idx;//下一个插入位置下标
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //拓扑排序
        n=numCourses;
        mark=new boolean[n];
        on=new boolean[n];
        ans=new int[n];
        idx=n-1;
        Deque<Integer>[] adj=new ArrayDeque[n];//邻接表
        //建图
        for (int i = 0; i < prerequisites.length; i++) {
            if(adj[prerequisites[i][1]]==null)
                adj[prerequisites[i][1]]=new ArrayDeque<>();
            adj[prerequisites[i][1]].offer(prerequisites[i][0]);
        }
        //从每个顶点开始，如果已经搜索则跳过，如果有环则退出
        for (int i = 0; i < n; i++) {
            if(flag)
                return new int[0];
            if (!mark[i]) {
                dfs(adj,i);
            }
        }
        return ans;
    }

    public void dfs(Deque<Integer>[] adj,int v){
        mark[v]=true;
        on[v]=true;
        if(adj[v]!=null){
            for (int w :adj[v]) {
                if(!mark[w]){
                    dfs(adj,w);
                } else if(on[w]){//已经标记的点，可能是之前遍历过的，也可能是本次路径上的
                    flag=true;
                    return;
                }
            }
        }
        on[v]=false;//回溯还原路径上点的状态
        ans[idx--]=v;//当该点没有指向，或已经遍历完后面的点，该点入栈
    }