public class TwoColorDetector {
    
    private boolean[] visited; 
    private boolean[] color;         // not only will we mark vertices as visited, we will give them a color!
    private boolean isTwoColorable;  // cached answer to the question -- is the graph two-colorable?
    
    public TwoColorDetector(Graph g) {
        visited = new boolean[g.numVertices()]; 
        color = new boolean[g.numVertices()];
        isTwoColorable = true;  // start with this assumption..
        for (int s = 0; s < g.numVertices(); s++)  // iterate through several "sources" s to search all connected components
            if (!visited[s])
                dfs(g,s);  
    }
    
    private void dfs(Graph g, int v) {  // i.e., do a dfs from v
        visited[v] = true;
        for (int w : g.adj(v)) {
            if (!visited[w]) {
                color[w] = !color[v];  // color it the other color so adj v and w are different colors
                dfs(g,w);
            }
            else if (color[w] == color[v])    // note, the vertex u where v came from will always be ok    
                isTwoColorable = false;       // as v's color was chosen opposite of u's color.  also,
        }                                     // for other visited vertices encountered, we'd have a cycle
    }                                         // but these are not automatically disqualifying -- only if 
                                              // the cycle is of odd length, which makes the colors of w and v agree
    
    public boolean isTwoColorable() {   // once established by the constructor, we just retrieve the cached result
        return this.isTwoColorable;
    }
    
    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);  // comment these two edges out to see a graph that IS two-colorable/bipartite,
        g.addEdge(2, 6);  // but still has cycles (albeit only even-length cycles)
        g.addEdge(2, 3);
        g.addEdge(2, 5);
        g.addEdge(3, 4);
        g.addEdge(4, 5);
        System.out.println(g);
        TwoColorDetector cdg = new TwoColorDetector(g);
        System.out.println("two-colorable? " + cdg.isTwoColorable() + "\n");
        
        Graph h = new Graph(7);
        h.addEdge(0, 1);
        h.addEdge(0, 5);
        h.addEdge(1, 2);
        h.addEdge(1, 4);
        h.addEdge(2, 5);
        h.addEdge(2, 6);
        h.addEdge(3, 4);
        System.out.println(h);  // h is a tree, which are always two-colorable/bipartite

        TwoColorDetector cdh = new TwoColorDetector(h);
        System.out.println("two-colorable? " + cdh.isTwoColorable());
    }
}