package algs41;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac Biconnected.java
 *  Dependencies: Graph.java
 *
 *  Identify articulation points and print them out.
 *  This can be used to decompose a graph into biconnected components.
 *  Runs in O(E + V) time.
 *
 *  http://www.cs.brown.edu/courses/cs016/book/slides/Connectivity2x2.pdf
 *
 *************************************************************************/

public class XBiconnected {
	private final int[] low;
	private final int[] pre;
	private int cnt;
	// private int bridges;
	private final boolean[] articulation;

	public XBiconnected(Graph G) {
		low = new int[G.V()];
		pre = new int[G.V()];
		articulation = new boolean[G.V()];
		for (int v = 0; v < G.V(); v++) low[v] = -1;
		for (int v = 0; v < G.V(); v++) pre[v] = -1;

		for (int v = 0; v < G.V(); v++)
			if (pre[v] == -1)
				dfs(G, v, v);
	}

	private void dfs(Graph G, int u, int v) {
		int children = 0;
		pre[v] = cnt++;
		low[v] = pre[v];
		for (int w : G.adj(v)) {
			if (pre[w] == -1) {
				children++;
				dfs(G, v, w);

				// update low number
				low[v] = Math.min(low[v], low[w]);

				// non-root of DFS is an articulation point if low[w] >= pre[v]
				if (low[w] >= pre[v] && u != v)
					articulation[v] = true;
			}

			// update low number - ignore reverse of edge leading to v
			else if (w != u)
				low[v] = Math.min(low[v], pre[w]);
		}

		// root of DFS is an articulation point if it has more than 1 child
		if (u == v && children > 1)
			articulation[v] = true;
	}

	// is vertex v an articulation point?
	public boolean isArticulation(int v) { return articulation[v]; }

	// test client
	public static void main(String[] args) {
		args = new String [] { "6", "6" };
		int V = Integer.parseInt(args[0]);
		int E = Integer.parseInt(args[1]);
		Graph G = GraphGenerator.simple(V, E);
		G.toGraphviz ("g");
		StdOut.println(G);

		XBiconnected bic = new XBiconnected(G);

		// print out articulation points
		StdOut.println();
		StdOut.println("Articulation points");
		StdOut.println("-------------------");
		for (int v = 0; v < G.V(); v++)
			if (bic.isArticulation(v)) StdOut.println(v);
	}


}