// 有向圖
 
public class Digraph {
    // 記錄頂點(diǎn)的數(shù)量
     
    private final int V;
 
    //記錄邊的數(shù)量
    private int E;
 
    //定義有向圖的鄰接表
    private Queue <Integer>[] adj;
 
    public Digraph (int v) {
        //初始化頂點(diǎn)數(shù)量
        this.V = v;
        //初始化邊的數(shù)量
        this.E = 0;
        //初始化鄰接表
        adj = new LinkedList[v];
        //初始化鄰接表的空隊(duì)列
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }
    public int V () {
        return V;
    }
    public int E () {
        return E;
    }
 
    //添加一條 v -> w的有向邊
    public void addEage (int v , int w) {
        adj[v].add(w);
        ++E;
    }
 
    //獲取頂點(diǎn)v 指向的 所有頂點(diǎn)
    public Queue<Integer> adj (int v) {
        return adj[v];
    }
 
    //將有向圖 反轉(zhuǎn) 后返回
    public Digraph reverse () {
        //創(chuàng)建一個(gè)反向圖
        Digraph reverseDigraph = new Digraph(V);
        //獲取原來有向圖的每個(gè)結(jié)點(diǎn)
        for (int i = 0; i < V; i++) {
            //獲取每個(gè)結(jié)點(diǎn) 鄰接表的所有結(jié)點(diǎn)
            for (Integer w : adj[i]) {
                //反轉(zhuǎn)圖記錄下 w -> v
                reverseDigraph.adj(w).add(i);
            }
        }
        return reverseDigraph;
    }
}
 

 
/**
 *  檢查圖中是否存在環(huán)
 */
public class DirectedCycle {
    /**
     * 索引代表頂點(diǎn)，用來記錄頂點(diǎn)是否被搜索過
     */
    private boolean[] marked;
 
    /**
     * 判斷圖中是否有環(huán)
     */
    private boolean hasCycle;
 
    /**
     * 采用棧的思想，記錄當(dāng)前頂點(diǎn)是否已經(jīng)存在 當(dāng)前搜索的的路徑上
     * 存在則可以判斷 圖中是存在環(huán)的
     */
    private boolean[] onStack;
 
    /**
     * 判斷傳入的有向圖 是否存在環(huán)
     * @param G
     */
    public DirectedCycle (Digraph G) {
        marked = new boolean[G.V()];
        onStack = new boolean[G.V()];
        hasCycle = false;
        //因?yàn)椴恢缽哪莻€(gè)點(diǎn)出發(fā) 可能存在環(huán)
        //所以需要從所有的頂點(diǎn)都出發(fā)搜索 判斷是否存在環(huán)
        for (int i = 0; i < G.V(); i++) {
            dfs(G,i);
        }
    }
 
    /**
     * 采用深度搜索 判斷有向圖是否存在環(huán)
     * onStack 入棧出棧 然后判斷當(dāng)前搜索的頂點(diǎn)是否已經(jīng)在搜索路徑上
     *
     * @param G
     * @param v
     */
    private void dfs (Digraph G,int v) {
        //標(biāo)記頂點(diǎn)已經(jīng)搜索過
        marked[v] = true;
        for (Integer adj : G.adj(v)) {
            //判斷v 是否已經(jīng)在搜索的路徑上了
            if(marked[adj] && onStack[adj]) {
                //存在環(huán)
                hasCycle = true;
            }else {
                //采用回溯的思路
                //讓頂點(diǎn)入棧
                onStack[adj] = true;
                dfs(G,adj);
                //回溯 頂點(diǎn)出棧
                onStack[adj] = false;
            }
        }
    }
 
    /**
     * 判斷是否存在環(huán)
     * @return
     */
    public boolean hasCycle(){
        return hasCycle;
    }
 
}

 
/**
 * 深度優(yōu)先搜索 的頂點(diǎn)排序
 */
public class DepthFirstOrder {
    /**
     * 索引代表頂點(diǎn) ，用來記錄頂點(diǎn)是否已經(jīng)被搜索過了
     */
    private boolean[] marked;
 
    /**
     * 使用棧記錄深度優(yōu)先搜索下的頂點(diǎn)
     */
    private Stack<Integer> reversePost;
 
    public DepthFirstOrder (Digraph G) {
        marked = new boolean[G.V()];
        reversePost = new Stack<>();
        for (int i = 0; i < G.V(); i++) {
            //如果頂點(diǎn)已經(jīng)被搜索過則不用
            if(!marked[i])
                dfs(G,i);
        }
    }
 
    /**
     * 基于深度優(yōu)先搜索，生成頂點(diǎn)線性序列
     * @param G
     * @param v
     */
    private void dfs (Digraph G, int v) {
        //標(biāo)記頂點(diǎn)已經(jīng)被搜索過
        marked[v] =  true;
        for (Integer w : G.adj(v)) {
            if(!marked[w])
                dfs(G,w);
        }
        //記錄到線性序列中
        reversePost.push(v);
    }
 
    /**
     * 獲取頂點(diǎn)線性序列
     * @return
     */
    private Stack<Integer> ReversePost() {
        return reversePost;
    }
}