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();
		}
	}


}