/**
 * 有向圖是否存在環(huán)
 *
 * @author alvin
 * @date 2022/11/2
 * @since 1.0
 **/
public class DirectedCycle {
    //索引代表頂點，值表示當(dāng)前頂點是否已經(jīng)被搜索
    private boolean[] marked;
    //記錄圖中是否有環(huán)
    private boolean hasCycle;
    //索引代表頂點，使用棧的思想，記錄當(dāng)前頂點有沒有已經(jīng)處于正在搜索的有向路徑上
    private boolean[] onStack;

    //創(chuàng)建一個檢測環(huán)對象，檢測圖G中是否有環(huán)
    public DirectedCycle(Digraph G){
        //初始化marked數(shù)組
        this.marked = new boolean[G.V()];
        //初始化hasCycle
        this.hasCycle = false;
        //初始化onStack數(shù)組
        this.onStack = new boolean[G.V()];

        //找到圖中每一個頂點，讓每一個頂點作為入口，調(diào)用一次dfs進行搜索
        for (int v =0; v<G.V();v++){
            //判斷如果當(dāng)前頂點還沒有搜索過，則調(diào)用dfs進行搜索
            if (!marked[v]){
                dfs(G,v);
            }
        }
    }

    //基于深度優(yōu)先搜索，檢測圖G中是否有環(huán)
    private void dfs(Digraph G, int v){
        //把頂點v表示為已搜索
        marked[v] = true;
        //把當(dāng)前頂點進棧
        onStack[v] = true;

        for(Integer w: G.adj(v)) {
            //判斷如果當(dāng)前頂點w沒有被搜索過，則繼續(xù)遞歸調(diào)用dfs方法完成深度優(yōu)先搜索
            if(!marked[w]) {
                dfs(G, w);
            }

            //判斷當(dāng)前頂點w是否已經(jīng)在棧中，如果已經(jīng)在棧中，證明當(dāng)前頂點之前處于正在搜索的狀態(tài)，那么現(xiàn)在又要搜索一次，證明檢測到環(huán)了
            if (onStack[w]){
                hasCycle = true;
                return;
            }
        }
        //把當(dāng)前頂點出棧
        onStack[v] = false;
    }

    //判斷當(dāng)前有向圖G中是否有環(huán)
    public boolean hasCycle(){
        return hasCycle;
    }
}

/**
 * 頂點排序
 *
 * @author alvin
 * @date 2022/11/2
 * @since 1.0
 **/
public class DepthFirstOrder {
    //索引代表頂點，值表示當(dāng)前頂點是否已經(jīng)被搜索
    private boolean[] marked;
    //使用棧，存儲頂點序列
    private Stack<Integer> reversePost;

    //創(chuàng)建一個檢測環(huán)對象，檢測圖G中是否有環(huán)
    public DepthFirstOrder(Digraph G){
        //初始化marked數(shù)組
        this.marked = new boolean[G.V()];
        //初始化reversePost棧
        this.reversePost = new Stack<>();

        //遍歷圖中的每一個頂點，讓每個頂點作為入口，完成一次深度優(yōu)先搜索
        for (int v = 0;v<G.V();v++){
            if (!marked[v]){
                dfs(G,v);
            }
        }
    }

    //基于深度優(yōu)先搜索，把頂點排序
    private void dfs(Digraph G, int v){
        //標(biāo)記當(dāng)前v已經(jīng)被搜索
        marked[v] = true;
        //通過循環(huán)深度搜索頂點v
        for (Integer w : G.adj(v)) {
            //如果當(dāng)前頂點w沒有搜索，則遞歸調(diào)用dfs進行搜索
            if (!marked[w]){
                dfs(G,w);
            }
        }
        //讓頂點v進棧
        reversePost.push(v);
    }

    //獲取頂點線性序列
    public Stack<Integer>  reversePost(){
        return reversePost;
    }
}

/**
 * 拓撲排序
 *
 * @author alvin
 * @date 2022/11/2
 * @since 1.0
 **/
public class TopoLogical {
    //頂點的拓撲排序
    private Stack<Integer> order;

    //構(gòu)造拓撲排序?qū)ο?
    public TopoLogical(Digraph G) {
        //創(chuàng)建一個檢測有向環(huán)的對象
        DirectedCycle cycle = new DirectedCycle(G);
        //判斷G圖中有沒有環(huán)，如果沒有環(huán)，則進行頂點排序：創(chuàng)建一個頂點排序?qū)ο?
        if (!cycle.hasCycle()){
            DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
            order = depthFirstOrder.reversePost();
        }
    }

    //判斷圖G是否有環(huán)
    private boolean isCycle(){
        return order==null;
    }

    //獲取拓撲排序的所有頂點
    public Stack<Integer> order(){
        return order;
    }
}

public class TopoLogicalTest {

    @Test
    public void test() {
        //準(zhǔn)備有向圖
        Digraph digraph = new Digraph(6);
        digraph.addEdge(0,2);
        digraph.addEdge(0,3);
        digraph.addEdge(2,4);
        digraph.addEdge(3,4);
        digraph.addEdge(4,5);
        digraph.addEdge(1,3);

        //通過TopoLogical對象堆有向圖中的頂點進行排序
        TopoLogical topoLogical = new TopoLogical(digraph);

        //獲取頂點的線性序列進行打印
        Stack<Integer> order = topoLogical.order();
        StringBuilder sb = new StringBuilder();
        while (order.size() != 0) {
            sb.append(order.pop()+"->");
        };
        String str = sb.toString();
        int index = str.lastIndexOf("->");
        str = str.substring(0,index);
        System.out.println(str);
    }
}