There are many articles online about graphs and (1-)connected components, but not many about biconnected components (BCCs), even though these are way more interesting and can be used to solve many problems! Especially in competitive programming it is vital to know about this concept.
I will outline what biconnected components are, how they work similar to/different from connected components, and how to find them algorithmically (with C++ code included). Presumed knowledge is knowing what a graph is. Sections:
Let's introduce the concept by looking at a problem that BCCs could help solve.
Charlotte is a secret agent for Enforcement of Metro Integrity (EMI), and she is tasked with transporting a top-secret package from one of her informants, Alice, to an undercover agent, Bob. Alice and Bob must not meet each other, because that would ruin the safety of the mission, so they must be at different metro stations, and Charlotte can naturally only use the metro network for transport. The matter is further complicated by the fact that Eve, Charlotte's adversary, is trying to sabotage the mission by disabling one unknown metro connection! For the sets of meeting locations \( A \) where Alice can meet and \( B \) where Bob can meet, how many possible pairs \( (a, b) \) are there such that Charlotte can safely transport the package from \( a \) to \( b \) no matter which line Eve disables?
Example metro network 1: nodes in the \( A \) set are marked with an A, nodes in the \( B \) set are marked with a B; an example valid pair of locations would be \( (3, 1) \), because no matter which metro line Eve chooses to sabogate, there is still a path from \( 3 \) to \( 1 \).
The metro network is a graph \( G \) with \( n \) nodes (metro stations) and \( m \) edges (metro lines). \( A \) and \( B \) are then subsets of the set of nodes \( V(G) \). We are trying to find an algorithm with the best possible running time. We can use the following definition to make the objective a bit more precise:
Definition: two nodes \( a, b \) are edge-biconnected if for any edge \( e \), there exists a path from \( a \) to \( b \) that does not go through \( e \).
Then in this problem we are trying to count the number of pairs \( (a, b) \) with \( a \in A \) and \( b \in B \) that are edge-biconnected. After all, no matter what edge Eve sabotages, we always still have a path between the two nodes.
The most naive algorithm would be to consider each \( a \in A \) and \( b \in B \). We would then go over each edge, remove it, and check if there is still a path from \( a \) to \( b \) using a simple graph traversal. This approach would have a time complexity of \( O(|A| \cdot |B| \cdot m \cdot (n + m)) \), which is very bad.
We could try to speed up this approach by precomputing for each edge the connected components (CCs) of the graph without that edge, making the path checking constant time. First we would start with the set of all \( (a, b) \) pairs, and iteratively remove pairs that we find can be blocked off by Eve's sabotage. Then we would iterate over each of the \( m \) edges, and: (1) remove it and compute for each node in which connected component it lies (\( O(m + n) \) time using a simple graph traversal), and (2) for each \( (a, b) \) pair, remove it if they do not both lie in the same connected component (now a constant time operation, so \( O(|A| \cdot |B|) \) overall). This leads to to a complexity of \( O(m \cdot ((n + m) + |A| \cdot |B|)) \), which is definitely an improvement, and we considered how to leverage connected components. Click through the animation below to see how this algorithm would work (the dashed circles indicate connected components with the edge removed). However, the running time is still quite miserable.
... continue reading