import java.util.ArrayList;

public class CycleDetection {

private Graph G;

private boolean[] visited;

private boolean hasCycle = false;

public CycleDetection(Graph G){

if(G.isDirected())

throw new IllegalArgumentException("只支持无向图");

this.G = G;

visited = new boolean[G.V()];

// 多包一层for，防止有多个联通分量

for(int v = 0 ;v<G.V();v++){

if(!visited[v])

if(dfs(v,v)) {

hasCycle = true;break;

}

}

}

// 从顶点v开始，判断图中是否有环

private boolean dfs(int v,int parent){

visited[v] = true;

// 遍历相邻节点

for(int w : G.adj(v)){

if(!visited[w])

if(dfs(w,v)) return true; //

else if(w != parent) // 判断是否有环：一个相邻节点w被访问过并且 该相邻节点w不是当前节点v的上个节点，则说明有环

return true;

}

return false;

}

// 是否有环

public boolean hasCycle(){

return hasCycle;

}

public static void main(String[] args){

Graph g = new Graph("g.txt");

CycleDetection cycleDetection = new CycleDetection(g);

System.out.println(cycleDetection.hasCycle());

Graph g2 = new Graph("g8.txt",true);

CycleDetection cycleDetection2 = new CycleDetection(g2);

System.out.println(cycleDetection2.hasCycle());

}

}