/**
 * 有向图检测环
 */public class DetectCycle {
    private boolean[] marked;
    private boolean hasCycle;
    private boolean[] onStack; //索引代表顶点，记录当前顶点有没有在搜索的路径上

    public DetectCycle(DiGraph diGraph) {
        marked = new boolean[diGraph.getV()];
        onStack = new boolean[diGraph.getV()];
        for (int i = 0; i < diGraph.getV(); i++) {
            if (!marked[i]) {
                dfs(diGraph, i);
            }
        }

    }

    private void dfs(DiGraph diGraph, int v) {
        marked[v] = true;
        onStack[v] = true;
        for (Integer w : diGraph.adj(v)) {
            if (!marked[w]) {
                dfs(diGraph, w);
            }
            //判断当前顶点是否已在onStack中，
            if (onStack[w]) {
                hasCycle = true;
                return;
            }
        }
        onStack[v] = false; //之所以有这一步，是将onStack还原，毕竟是个经常被调用的方法，不还原就成了一次性用品
    }

    public boolean hasCycle() {
        return hasCycle;
    }

}