package algs41;
import stdlib.*;
import algs13.Stack;
/* ***********************************************************************
 *  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 final boolean[] color;   // color[v] gives vertices on one side of bipartition
  private final boolean[] marked;  // marked[v] = true if v has been visited in DFS
  private final 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<>();
        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.format("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.format("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
    args = new String [] { "200", "100", "20" };
    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();
    }
  }


}