public class CycleDetector {
    
    private boolean[] visited; 
    private boolean hasCycle;  // cached answer to the question - does the graph have a cycle?
    
    public CycleDetector(Graph g) {
        visited = new boolean[g.numVertices()]; 
        hasCycle = false; //superfluous
        for (int s = 0; s < g.numVertices(); s++)  // iterate through several "sources" s to search all connected components
            if (!visited[s])
                dfs(g,s,s);  // note the additional argument! (see comment concerning special case in dfs() method below)
    }
    
    private void dfs(Graph g, int v, int u) {  // i.e., do a dfs from v, (which came from u)
        visited[v] = true;
        for (int w : g.adj(v)) {
            if (!visited[w]) {
                dfs(g,w,v);
            }
            else if (w != u)       // if v came from u, then u will be one of the vertices w adjacent to v,
                hasCycle = true;   // and u will ALWAYS be already visited -- so we expect visited[u]==true.  But if we reach
        }                          // out from w and find some other visited vertex, we've got a cycle!
    }                              // SPECIAL CASE: sources s don't "come from" anywhere.  By calling dfs() with u = v for these,
                                   // note that the "else if" would execute for EVERY visited adj w to s -- but when the source s
                                   // is first considered, all visited vertices are in a different component, so the "else if"
                                   // NEVER executes for a source (which is good, as it is too early to form a cycle)
    
    public boolean hasCycle() {   // once established by the constructor, we just retrieve the cached result
        return this.hasCycle;
    }
    
    public static void main(String[] args) {
        
        Graph g = new Graph(7);
        g.addEdge(0, 1);
        g.addEdge(0, 6);
        g.addEdge(1, 3);
        g.addEdge(1, 5);
        g.addEdge(1, 6);
        g.addEdge(2, 3);
        g.addEdge(2, 5);
        g.addEdge(2, 6);
        g.addEdge(3, 4);
        g.addEdge(4, 5);
        System.out.println(g);
        
        Graph h = new Graph(7);
        h.addEdge(0, 1);
        h.addEdge(1, 2);
        h.addEdge(1, 4);
        h.addEdge(2, 5);
        h.addEdge(2, 6);
        h.addEdge(3, 4);
        System.out.println(h);
        
        CycleDetector cdg = new CycleDetector(g);
        System.out.println(cdg.hasCycle());
        
        CycleDetector cdh = new CycleDetector(h);
        System.out.println(cdh.hasCycle());
    }
}