content: /*************************************************************************
   *  Compilation:  javac Bipartite.java
   *  Dependencies: Graph.java 
   *
   *  Given a graph, find either (i) a bipartition or (ii) an odd-length cycle.
   *  Runs in O(E + V) time.
   *
   *
   *************************************************************************/
  
  public class Bipartite {
      private boolean isBipartite;   // is the graph bipartite?
      private boolean[] color;       // color[v] gives vertices on one side of bipartition
      private boolean[] marked;      // marked[v] = true if v has been visited in DFS
      private int[] edgeTo;          // edgeTo[v] = last edge on path to v
      private Stack<Integer> cycle;  // odd-length cycle
  
      public Bipartite(Graph G) {
          isBipartite = true;
          color  = new boolean[G.V()];
          marked = new boolean[G.V()];
          edgeTo = new int[G.V()];
  
          for (int v = 0; v < G.V(); v++) {
              if (!marked[v]) {
  //                color[v] = false;
                  dfs(G, v);
              }
          }
          assert check(G);
      }
  
      private void dfs(Graph G, int v) { 
          marked[v] = true;
          for (int w : G.adj(v)) {
  
              // short circuit if odd-length cycle found
              if (cycle != null) return;
  
              // found uncolored vertex, so recur
              if (!marked[w]) {
                  edgeTo[w] = v;
                  color[w] = !color[v];
                  dfs(G, w);
              } 
  
              // if v-w create an odd-length cycle, find it
              else if (color[w] == color[v]) {
                  isBipartite = false;
                  cycle = new Stack<Integer>();
                  cycle.push(w);  // don't need this unless you want to include start vertex twice
                  for (int x = v; x != w; x = edgeTo[x]) {
                      cycle.push(x);
                  }
                  cycle.push(w);
              }
          }
      }
  
      boolean isBipartite()            { return isBipartite; }
      boolean color(int v)             { return color[v];    }
      public Iterable<Integer> cycle() { return cycle;       }
  
      private boolean check(Graph G) {
          // graph is bipartite
          if (isBipartite) {
              for (int v = 0; v < G.V(); v++) {
                  for (int w : G.adj(v)) {
                      if (color[v] == color[w]) {
                          System.err.printf("edge %d-%d with %d and %d in same side of bipartition\n", v, w, v, w);
                          return false;
                      }
                  }
              }
          }
  
          // graph has an odd-length cycle
          else {
              // verify cycle
              int first = -1, last = -1;
              for (int v : cycle()) {
                  if (first == -1) first = v;
                  last = v;
              }
              if (first != last) {
                  System.err.printf("cycle begins with %d and ends with %d\n", first, last);
                  return false;
              }
          }
  
          return true;
      }
  
      public static void main(String[] args) {
          // create random bipartite graph with V vertices and E edges; then add F random edges
          int V = Integer.parseInt(args[0]);
          int E = Integer.parseInt(args[1]);
          int F = Integer.parseInt(args[2]);
  
          Graph G = new Graph(V);
          int[] vertices = new int[V];
          for (int i = 0; i < V; i++) vertices[i] = i;
          StdRandom.shuffle(vertices);
          for (int i = 0; i < E; i++) {
              int v = StdRandom.uniform(V/2);
              int w = StdRandom.uniform(V/2);
              G.addEdge(vertices[v], vertices[V/2 + w]);
          }
  
          // add F extra edges
          for (int i = 0; i < F; i++) {
              int v = (int) (Math.random() * V);
              int w = (int) (Math.random() * V);
              G.addEdge(v, w);
          }
  
          StdOut.println(G);
  
  
          Bipartite b = new Bipartite(G);
          if (b.isBipartite()) {
              StdOut.println("Graph is bipartite");
              for (int v = 0; v < G.V(); v++) {
                  StdOut.println(v + ": " + b.color(v));
              }
          }
          else {
              StdOut.print("Graph has an odd-length cycle: ");
              for (int x : b.cycle()) {
                  StdOut.print(x + " ");
              }
              StdOut.println();
          }
      }
  
  
  }
  