Applications of Bridges & Articulation Points

March 2026 · 18 min read

The previous posts built up the theory and algorithms for finding bridges and articulation points. This post is about putting that theory to work. We cover the most important real-world applications, the data structures built on top of bridge and AP detection, and a curated set of practice problems to solidify your understanding.

Network Reliability Analysis

The original motivation for studying bridges and articulation points comes from network engineering. A bridge in a network is a link whose failure disconnects the network. An articulation point is a node whose failure disconnects the network. Both represent single points of failure.

Consider a corporate network connecting six offices. Traffic flows along the edges. If any single link or router goes down, does the entire network stay connected?

Running Tarjan's algorithm on this network immediately identifies D and E as articulation points and the edge D‑E as a bridge. The engineering response is straightforward: add a redundant link between the two clusters (for example, C‑G) so that no single failure can partition the network.

Other real-world domains

• Transportation: A bridge in a road network is a road whose closure isolates a town. City planners use this analysis to prioritize road maintenance.
• Power grids: An articulation point in the grid graph is a substation whose failure causes a blackout in an entire region.
• Social networks: An articulation point in a social graph is a person who connects two otherwise separate communities. Removing that person fractures the community.
• Biology: In protein interaction networks, bridges represent essential interactions whose disruption kills the cell.

Biconnected Components

A graph is biconnected if it is connected and has no articulation points. Equivalently, between every pair of vertices there exist at least two vertex-disjoint paths. A biconnected component (also called a 2-connected component or block) is a maximal biconnected subgraph.

The key insight: articulation points are shared between biconnected components. Every non-AP vertex belongs to exactly one biconnected component. Every AP belongs to two or more.

How bridges and APs partition the graph

The biconnected component decomposition works as follows:

1. Run DFS and find all articulation points.
2. Maintain a stack of edges during the DFS.
3. When you identify a biconnected component (the subtree rooted at a child of an AP has low[child] >= disc[node]), pop all edges from the stack until you reach the current edge. Those edges form one biconnected component.
4. A bridge is a biconnected component that contains exactly one edge.

The algorithm for finding biconnected components runs in O(V + E) time, the same as a single DFS traversal. You simply augment the articulation point algorithm with an edge stack.

void dfs(int u, int parent, int& timer,
         vector<vector<int>>& adj,
         vector<int>& disc, vector<int>& low,
         stack<pair<int,int>>& st,
         vector<vector<pair<int,int>>>& components) {
    disc[u] = low[u] = timer++;
    int children = 0;
    for (int v : adj[u]) {
        if (disc[v] == -1) {
            children++;
            st.push({u, v});
            dfs(v, u, timer, adj, disc, low, st, components);
            low[u] = min(low[u], low[v]);
            // Check if u is an AP or root with multiple children
            bool isAP = (parent == -1 && children > 1)
                      || (parent != -1 && low[v] >= disc[u]);
            if (isAP) {
                // Pop edges until (u, v) to form a component
                vector<pair<int,int>> comp;
                while (st.top() != make_pair(u, v)) {
                    comp.push_back(st.top());
                    st.pop();
                }
                comp.push_back(st.top());
                st.pop();
                components.push_back(comp);
            }
        } else if (v != parent && disc[v] < disc[u]) {
            st.push({u, v});
            low[u] = min(low[u], disc[v]);
        }
    }
}

Block-Cut Tree

Once you have the biconnected component decomposition, the next natural step is to build the block-cut tree. This is a tree where:

• Each biconnected component (block) becomes a node.
• Each articulation point (cut vertex) becomes a node.
• An edge connects a block node to a cut vertex node if the cut vertex belongs to that block.

The result is always a tree (or a forest if the original graph is disconnected). The block-cut tree compresses the structure of the graph: all cycles within a block are collapsed into a single node, and the tree captures how the blocks are glued together via cut vertices.

Why is this useful?

Many graph problems become tree problems on the block-cut tree. Since tree problems are generally much easier (LCA, path queries, subtree queries), this transformation is extremely powerful. For example:

• Counting paths: The number of vertices that become disconnected when a cut vertex is removed equals the sum of sizes of the subtrees hanging off that cut vertex in the block-cut tree.
• Minimum vertex cuts: Finding the minimum number of vertices to disconnect two nodes reduces to a path query on the block-cut tree.
• Dynamic connectivity: Updates to the graph can be reflected efficiently in the block-cut tree structure.

// Building the block-cut tree after finding biconnected components
// blocks[i] = set of vertices in block i
// is_cut[v] = true if v is a cut vertex
// Assign node IDs: blocks get IDs 0..num_blocks-1
//   cut vertices get IDs num_blocks..num_blocks+num_cuts-1

vector<vector<int>> tree(num_blocks + num_cuts);
for (int i = 0; i < num_blocks; i++) {
    for (int v : blocks[i]) {
        if (is_cut[v]) {
            int cut_id = num_blocks + cut_index[v];
            tree[i].push_back(cut_id);
            tree[cut_id].push_back(i);
        }
    }
}

2-Edge-Connected Components

A graph is 2-edge-connected if it remains connected after removing any single edge. The 2-edge-connected components are the maximal subgraphs that satisfy this property.

The relationship to bridges is direct: two vertices are in the same 2-edge-connected component if and only if every path between them avoids all bridges. Equivalently, if you remove all bridges from the graph, the remaining connected components are exactly the 2-edge-connected components.

The algorithm for finding 2-edge-connected components is simple once you have all bridges: remove bridges from the edge set, then find connected components in the remaining graph using BFS or DFS. Total time: O(V + E).

// After finding all bridges (stored in set bridge_edges):
vector<int> comp(n, -1);
int num_comp = 0;
for (int u = 0; u < n; u++) {
    if (comp[u] != -1) continue;
    // BFS/DFS using only non-bridge edges
    queue<int> q;
    q.push(u);
    comp[u] = num_comp;
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int w : adj[v]) {
            if (comp[w] == -1 &&
                !bridge_edges.count({min(v,w), max(v,w)})) {
                comp[w] = num_comp;
                q.push(w);
            }
        }
    }
    num_comp++;
}

After collapsing each 2-edge-connected component into a single supernode, the bridges become the edges of a tree. This is called the bridge tree and is the edge-connectivity analogue of the block-cut tree.

Finding All Bridges Online

In a dynamic graph where edges are added one at a time, we may want to maintain the set of bridges without rerunning Tarjan's algorithm from scratch after every insertion.

The online bridge-finding algorithm maintains a forest of 2-edge-connected components using a Disjoint Set Union (DSU) data structure. When a new edge (u, v) is added:

1. If u and v are in different connected components, the edge is a new bridge. Merge the components.
2. If u and v are in the same connected component, find the path between them in the current tree. All edges on this path cease to be bridges (because a cycle now exists through them). Merge all 2-edge-connected components along this path.

The amortized time per edge insertion is O(alpha(n)) where alpha is the inverse Ackermann function. This is nearly O(1) per operation, making it practical for competitive programming problems with online queries.

Practice Problems

The following problems test your understanding of bridges, articulation points, and the structures built on top of them. They are roughly ordered from direct application to problems requiring deeper insight.

Time and Space Complexity Summary

All the algorithms discussed in this series run in linear time. The table below summarizes the complexities for a graph with V vertices and E edges.

The linear time complexity makes these algorithms practical for competitive programming constraints of up to 10^5 or 10^6 vertices and edges. The space overhead is dominated by the adjacency list representation of the graph itself.

Further Reading

Bridges and articulation points deal with connectivity under removal. The natural extension is to study connectivity under edge direction:

• Strongly Connected Components extend the idea of connectivity to directed graphs. Tarjan's SCC algorithm is structurally very similar to the bridge-finding algorithm. If you understood the DFS tree, discovery times, and low values from this series, SCC will feel familiar.
• Disjoint Set Union is the foundation of the online bridge-finding algorithm and many connectivity problems.
• Euler Paths and Circuits are directly related to bridges. A connected graph has an Euler circuit if and only if every vertex has even degree. Bridges play a role in Fleury's algorithm for finding Euler paths.