``` 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 ``` ```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) { int V = Integer.parseInt(args[0]); int E = Integer.parseInt(args[1]); Graph G = new Graph(V, E); 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); } } ```