# Biconnected Component - [Biconnected component | Wikipedia](https://en.wikipedia.org/wiki/Biconnected_component) - **Definition:** In a biconnected graph - Either removal of an edge disconnects the graph (a single edge), or - Every three vertices in the component are contained in a simple cycle. - _Articulation vertex_: an intersection of two different biconnected component. There is only one articulation vertex, otherwise the two components would just be one. - Bi-connection provides fault tolerance. ## Solution - For vertex $v$, if a child $s$ of $v$ has $\text{Low}(s) \ge \text{DFS}\#(v)$, then $v$ is articulation vertex. (As there could be $s \leadsto v$, but $v$ has no back edge) $ \text{Low}(v) = \min\begin{cases} \text{DFS}\#(v) \\ \text{Low}(s), \text{ for each child } s \\ \text{DFS}\#(w), \text{ where } (v, w) \text{ is a back edge} \end{cases} $ - _Low-point_ is the lowest depth of neighbors and all descendants of $v$ (included) in the [[dfs|DFS]] tree ``` counter = 1, mark all vertices as not visited BICONNECTED-COMOPNENTS(V) mark v as visited DFS#(v) = counter counter += 1 Low(v) = DFS#(v) for each edge (v, w) if w not visited w.parent = v BICONNECTED-COMPONENT(w) Low(v) = min( Low(v), Low(w) ) if Low(w) >= DFS#(v) report v is an articulation vertex subgraph rooted at s and v forms a biconnected graph else if w != v.parent Low(v) = min( Low(v), DFS#(w) ) ```