⚙️AlgorithmIntermediate

Bridge Tree

Key Points

  • •
    A bridge tree is built by contracting every 2-edge-connected component of an undirected graph into a single node, leaving only bridges as edges between nodes.
  • •
    You can find all bridges in O(n + m) using a single DFS with low-link values, then label components by ignoring bridges.
  • •
    The distance between two contracted nodes in the bridge tree equals the number of bridges on any path between the original vertices.
  • •
    Two vertices are 2-edge-connected if and only if they map to the same node in the bridge tree (path length zero).
  • •
    For a connected graph, the bridge tree is a tree; for a disconnected graph, it is a forest.
  • •
    Path queries that count or check usage of certain edges are easy on the bridge tree via LCA and prefix sums.
  • •
    Be careful with multi-edges: an edge is not a bridge if there is a parallel edge; track edges by unique IDs to avoid false bridges.
  • •
    Preprocessing takes O(n + m) time and O(n + m) space; LCA adds O(N log N) for preprocessing and O(log N) per query, where N is number of components.

Prerequisites

  • →Depth-First Search (DFS) — Bridge detection and component labeling rely on DFS traversal and understanding parent/child and back-edges.
  • →Graph Representations (Adjacency Lists) — Efficiently iterating over neighbors and storing edge IDs is essential for linear-time processing and handling multi-edges.
  • →Trees and Forests — The bridge tree is a forest; queries and LCA require familiarity with tree properties.
  • →Lowest Common Ancestor (LCA) and Binary Lifting — Path queries on the bridge tree are typically implemented using LCA for O(log n) time per query.
  • →Big-O Notation — To understand linear-time bridge detection and the costs of preprocessing and queries.
  • →Connected Components — 2-edge-connected components are computed from connected components after removing bridges.
  • →Tarjan's Low-Link Technique — The standard way to find bridges in O(n + m) using discovery and low-link times.

Detailed Explanation

Tap terms for definitions

01Overview

A bridge tree is a compressed representation of an undirected graph that captures how its fragile connections (bridges) tie together robust regions. A bridge is an edge whose removal increases the number of connected components. Inside each region where every pair of vertices remains connected even if any single edge is deleted, the graph is called 2-edge-connected. The bridge tree contracts each such 2-edge-connected component into a single node and keeps only the bridges as edges between these nodes. The resulting structure is a forest (a collection of trees). If the original graph is connected, this forest is a single tree. This construction makes certain path questions dramatically simpler. For example, the number of bridges you must cross to travel between two vertices equals the distance between their component nodes in the bridge tree. Checking whether two vertices are 2-edge-connected reduces to checking whether they live in the same component node (i.e., the path between them in the bridge tree has zero edges). The bridge tree can be built in linear time after computing bridges via a standard DFS (Tarjan’s low-link method). Once the tree is built, lowest common ancestor (LCA) techniques allow fast path queries including counts over “must-use” bridges or existence of such edges on a path.

02Intuition & Analogies

Imagine a city map where most neighborhoods have many interconnecting streets, but some neighborhoods are connected to the rest of the city by a single narrow bridge. Inside a well-connected neighborhood, if one street is closed, you can still take alternate streets to get around. But if the only bridge connecting two neighborhoods is closed, the neighborhoods become isolated from each other. Now, shrink each neighborhood into a single dot. Keep the bridges between neighborhoods as lines. You’ve built the bridge tree: a simplified map showing how the fragile connections tie robust clusters together. Inside each dot, movement is resilient to a single road closure; only the inter-dot lines (bridges) are fragile. Why is this helpful? Suppose you want to know if reaching from house A to house B must cross any of the city’s fragile bridges. On the original city map, there are many possible routes to check. On the bridge tree, there is at most one simple path between the two dots (because trees have unique simple paths). The number of fragile bridges you must cross becomes the number of edges along that path. If this number is zero, A and B are in the same robust cluster and remain connected even if any one street fails. If some bridges are “special” (toll bridges, checkpoints), just mark those tree edges and count how many marked edges lie along the path using prefix sums or LCA-based techniques. This viewpoint extracts the essence of connectivity under single-edge failures and turns complicated path reasoning into clean tree computations.

03Formal Definition

Let G = (V, E) be a finite, simple or multigraph that is undirected. An edge e ∈ E is a bridge if removing e increases the number of connected components of G. A subset C ⊆ V is a 2-edge-connected component (2ECC) if for any u, v ∈ C, there exists a u–v path in G that avoids every individual edge failure; equivalently, u and v remain connected after the deletion of any single edge. The 2ECCs partition V and can be computed by deleting all bridges and taking the connected components of the remaining graph. The bridge tree (also called the bridge-block tree or bridge-connected components tree) of G is the graph T = (, ) where: - corresponds to the set of 2ECCs of G (each vertex in V belongs to exactly one component in ), and - contains an edge between components A, B ∈ for every bridge in G that has one endpoint in A and the other in B. Each connected component of G yields a tree in T; hence T is a forest. If G is connected, T is a tree. For any u, v ∈ V, denote by comp(u) the 2ECC containing u. Then the number of bridges on any u–v path in G equals the length (number of edges) of the unique simple path between comp(u) and comp(v) in T. In particular, u and v are 2-edge-connected if and only if comp(u) = comp(v).

04When to Use

Use the bridge tree when problems involve robustness to edge deletions, or when path queries depend only on bridges or subsets of bridges. Typical situations include:

  • Counting how many bridges any path from u to v must cross. In the bridge tree, this is simply the tree distance between comp(u) and comp(v).
  • Checking if two vertices are 2-edge-connected (answer is true iff they map to the same node in the bridge tree).
  • Answering queries about “must-use” edges: mark certain bridges (e.g., tolls, constraints), then count or detect marked edges along the path using LCA and prefix sums on the tree.
  • Aggregation on bridge-separated regions: compute per-component values (size, sum of weights), and push or pull values along the bridge tree for DP or centroid decompositions.
  • Preprocessing undirected graphs for later dynamic or offline queries in competitive programming: once built, the bridge tree supports many path queries in O(log N) or even O(1) with additional structures. Avoid using the bridge tree for vertex-failure robustness (use block-cut tree for articulation points and biconnected components), for directed graphs (use strongly connected components or 2-edge-connected directed notions), or when queries require internal structure within each 2ECC (then stay in the original graph or augment each supernode).

⚠️Common Mistakes

  • Ignoring multi-edges: If two vertices are connected by at least two parallel edges, neither is a bridge. In low-link DFS, skipping only by parent vertex (instead of parent edge ID) can misclassify bridges when parallel edges exist. Always track and skip by unique edge IDs.
  • Wrong bridge condition: The correct test for DFS tree edge (u, v) is bridge if low[v] > tin[u], not ≥. Using ≥ turns back-edges into bridges incorrectly.
  • Forgetting disconnected graphs: The bridge tree is a forest. LCA or depth computations must be run for each tree component. For queries between nodes in different trees, report “disconnected” or a sentinel.
  • Recursion depth limits: A deep DFS on large inputs can overflow the stack. Consider iterative DFS or increase stack size when needed.
  • Mixing vertex- and edge-biconnectivity: Articulation points and block-cut trees address vertex failures, not edge failures. Use the correct structure for the problem.
  • Not clearing/reinitializing arrays between tests: In multi-test problems, stale data in tin/low/isBridge/adj causes hard-to-find bugs.
  • Off-by-one indexing: Be consistent about 0-based vs 1-based node IDs when storing edges and building component indices.
  • Forgetting to rebuild the tree after changes: If the graph changes (edge additions/deletions), the previously computed bridge tree may be invalid. For online dynamic changes, specialized data structures are needed.

Key Formulas

Low-link Recurrence

Explanation: The lowest discovery time reachable from u is the minimum of its own discovery time, any ancestor reachable via a back-edge, and the low values of its DFS children. This powers Tarjan’s bridge detection.

Bridge Test

Explanation: If the subtree rooted at v cannot reach u or any ancestor of u via a back-edge (low[v] is strictly greater), then removing (u,v) disconnects the graph.

Bridge Detection Complexity

Explanation: A single DFS computes all discovery and low-link values in time linear in the number of vertices n and edges m.

Tree Distance via LCA

Explanation: In a rooted tree, the number of edges between a and b can be computed using their depths and lowest common ancestor. This equals the number of bridges between their corresponding vertices in the original graph.

2-edge-connected Criterion

Explanation: After contracting 2-edge-connected components, vertices share the same supernode exactly when every u–v path can avoid any single-edge deletion.

Bridge Tree Sizes

Explanation: Every bridge becomes exactly one tree edge. When the original graph is connected, the contracted graph is a tree so edges equal vertices minus one.

Ancestor Test by Euler Tour

Explanation: Using entry and exit times from a DFS on the tree, one can test ancestor relationships in O(1), which helps in LCA and path-sum computations.

Complexity Analysis

Building a bridge tree proceeds in three main stages. First, find all bridges using a DFS with low-link values. Each edge is explored at most twice (once from each endpoint), and each vertex is visited once, so the time is O(n + m) and the space is O(n + m) for adjacency and O(n) for arrays tin, low, and bookkeeping. Second, remove (ignore) bridges and run a DFS/BFS to label 2-edge-connected components; this also costs O(n + m) time and O(n) space. Third, build the bridge tree by adding an edge between the component IDs for every original bridge; this is O(#bridges) ≤ O(m) time and O(#components + #bridges) space. If you need fast path queries on the bridge tree, preprocess LCA with binary lifting: building parent pointers up to ⌈log2 N⌉ for of components costs O(N log N) time and O(N log N) space; a query for the number of bridges between two original vertices then takes O(log N) time (to compute LCA and derive distance). If you also store a prefix sum of marked bridges along parent edges, counting marked bridges on a path is also O(log N). These complexities are typically dominated by the initial O(n + m) pass on the original graph, as and #. For very large and deep graphs, recursion depth can be a practical issue; an iterative DFS or tail recursion elimination can mitigate stack overflows without changing asymptotic bounds.

Code Examples

Build the Bridge Tree: Find Bridges, Label 2ECCs, Construct Forest
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Edge { int u, v; };
5
6int main() {
7    ios::sync_with_stdio(false);
8    cin.tie(nullptr);
9
10    int n, m;
11    if (!(cin >> n >> m)) return 0;
12
13    vector<Edge> edges(m);
14    vector<vector<pair<int,int>>> adj(n+1);
15    for (int i = 0; i < m; ++i) {
16        int u, v; cin >> u >> v;
17        edges[i] = {u, v};
18        adj[u].push_back({v, i});
19        adj[v].push_back({u, i});
20    }
21
22    // 1) Find bridges using Tarjan's low-link
23    vector<int> tin(n+1, -1), low(n+1, -1);
24    vector<char> visited(n+1, false);
25    vector<char> isBridge(m, false);
26    int timer = 0;
27
28    function<void(int,int)> dfs = [&](int u, int peid) {
29        visited[u] = true;
30        tin[u] = low[u] = timer++;
31        for (auto [v, eid] : adj[u]) {
32            if (eid == peid) continue; // skip the edge we came from (by ID!)
33            if (visited[v]) {
34                // back-edge
35                low[u] = min(low[u], tin[v]);
36            } else {
37                dfs(v, eid);
38                low[u] = min(low[u], low[v]);
39                if (low[v] > tin[u]) {
40                    isBridge[eid] = true; // (u,v) is a bridge
41                }
42            }
43        };
44    };
45
46    for (int i = 1; i <= n; ++i) if (!visited[i]) dfs(i, -1);
47
48    // 2) Label 2-edge-connected components (ignore bridges)
49    vector<int> compId(n+1, -1);
50    int compCnt = 0;
51    function<void(int)> paint = [&](int s) {
52        stack<int> st; st.push(s); compId[s] = compCnt;
53        while (!st.empty()) {
54            int u = st.top(); st.pop();
55            for (auto [v, eid] : adj[u]) {
56                if (isBridge[eid]) continue; // do not cross bridges inside a component
57                if (compId[v] == -1) {
58                    compId[v] = compCnt;
59                    st.push(v);
60                }
61            }
62        }
63    };
64
65    for (int i = 1; i <= n; ++i) if (compId[i] == -1) { paint(i); ++compCnt; }
66
67    // 3) Build bridge tree (forest)
68    vector<vector<int>> tree(compCnt);
69    for (int eid = 0; eid < m; ++eid) if (isBridge[eid]) {
70        int a = compId[edges[eid].u];
71        int b = compId[edges[eid].v];
72        tree[a].push_back(b);
73        tree[b].push_back(a);
74    }
75
76    // Output: print bridges and the tree
77    cout << "Bridges (edge ids):\n";
78    for (int i = 0; i < m; ++i) if (isBridge[i]) {
79        cout << i << " (" << edges[i].u << "," << edges[i].v << ")\n";
80    }
81
82    cout << "\nComponent ID of each vertex:\n";
83    for (int i = 1; i <= n; ++i) cout << i << ": comp " << compId[i] << "\n";
84
85    cout << "\nBridge tree (forest) adjacency:\n";
86    for (int c = 0; c < compCnt; ++c) {
87        cout << c << ":";
88        for (int w : tree[c]) cout << ' ' << w;
89        cout << '\n';
90    }
91
92    return 0;
93}
94

This program reads an undirected graph, finds all bridges using low-link values, labels 2-edge-connected components by ignoring bridges, and builds the bridge tree as a forest. It prints bridge edges, the component ID for each original vertex, and the adjacency list of the resulting forest.

Time: O(n + m) for finding bridges and labeling components; O(#bridges) to build the tree.Space: O(n + m) for adjacency and DFS arrays; O(#components + #bridges) for the tree.
Queries: Number of Bridges Between Two Vertices and 2-Edge-Connectivity
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Edge { int u, v; };
5
6int main(){
7    ios::sync_with_stdio(false);
8    cin.tie(nullptr);
9
10    int n, m; cin >> n >> m;
11    vector<Edge> edges(m);
12    vector<vector<pair<int,int>>> adj(n+1);
13    for (int i = 0; i < m; ++i) {
14        int u, v; cin >> u >> v;
15        edges[i] = {u, v};
16        adj[u].push_back({v, i});
17        adj[v].push_back({u, i});
18    }
19
20    // 1) Bridges via Tarjan
21    vector<int> tin(n+1, -1), low(n+1, -1);
22    vector<char> vis(n+1, false), isBridge(m, false);
23    int timer = 0;
24    function<void(int,int)> dfs = [&](int u, int peid){
25        vis[u] = true; tin[u] = low[u] = timer++;
26        for (auto [v, eid] : adj[u]){
27            if (eid == peid) continue;
28            if (vis[v]) low[u] = min(low[u], tin[v]);
29            else {
30                dfs(v, eid);
31                low[u] = min(low[u], low[v]);
32                if (low[v] > tin[u]) isBridge[eid] = true;
33            }
34        }
35    };
36    for (int i = 1; i <= n; ++i) if (!vis[i]) dfs(i, -1);
37
38    // 2) Components ignoring bridges
39    vector<int> comp(n+1, -1);
40    int C = 0;
41    function<void(int)> paint = [&](int s){
42        stack<int> st; st.push(s); comp[s] = C;
43        while(!st.empty()){
44            int u = st.top(); st.pop();
45            for (auto [v, eid] : adj[u]){
46                if (isBridge[eid]) continue;
47                if (comp[v] == -1){ comp[v] = C; st.push(v); }
48            }
49        }
50    };
51    for (int i = 1; i <= n; ++i) if (comp[i] == -1){ paint(i); ++C; }
52
53    // 3) Build tree of components (forest)
54    vector<vector<int>> tree(C);
55    for (int eid = 0; eid < m; ++eid) if (isBridge[eid]){
56        int a = comp[edges[eid].u], b = comp[edges[eid].v];
57        tree[a].push_back(b);
58        tree[b].push_back(a);
59    }
60
61    // 4) LCA preprocessing on the forest
62    int LOG = 1; while ((1<<LOG) <= max(1,C)) ++LOG;
63    vector<int> depth(C, 0), rootOf(C, -1);
64    vector<vector<int>> up(LOG, vector<int>(C, -1));
65
66    function<void(int,int,int)> dfsTree = [&](int u, int p, int r){
67        up[0][u] = (p == -1 ? u : p);
68        rootOf[u] = r;
69        for (int j = 1; j < LOG; ++j) up[j][u] = up[j-1][ up[j-1][u] ];
70        for (int v : tree[u]) if (v != p){
71            depth[v] = depth[u] + 1;
72            dfsTree(v, u, r);
73        }
74    };
75    for (int i = 0; i < C; ++i) if (rootOf[i] == -1) dfsTree(i, -1, i);
76
77    auto lca = [&](int a, int b){
78        if (rootOf[a] != rootOf[b]) return -1; // different trees => no LCA
79        if (depth[a] < depth[b]) swap(a,b);
80        int k = depth[a] - depth[b];
81        for (int j = LOG-1; j >= 0; --j) if (k & (1<<j)) a = up[j][a];
82        if (a == b) return a;
83        for (int j = LOG-1; j >= 0; --j){
84            if (up[j][a] != up[j][b]){ a = up[j][a]; b = up[j][b]; }
85        }
86        return up[0][a];
87    };
88
89    auto distTree = [&](int a, int b){
90        int c = lca(a,b);
91        if (c == -1) return -1; // disconnected
92        return depth[a] + depth[b] - 2*depth[c];
93    };
94
95    int q; cin >> q;
96    // For each query (u,v): output number of bridges on any u-v path and whether 2-edge-connected
97    while (q--) {
98        int u, v; cin >> u >> v;
99        int a = comp[u], b = comp[v];
100        int d = distTree(a,b);
101        if (d == -1) {
102            cout << "-1 DISCONNECTED\n"; // no path exists in original graph
103        } else {
104            // d equals number of bridges between u and v
105            cout << d << ' ' << (d == 0 ? "YES" : "NO") << "\n";
106        }
107    }
108    return 0;
109}
110

This program builds the bridge tree and preprocesses LCA with binary lifting over the resulting forest. For each query (u, v), it computes the tree distance between comp(u) and comp(v), which equals the number of bridges on any path. If the distance is zero, u and v are 2-edge-connected; if they lie in different tree components, the answer is -1 (disconnected).

Time: O(n + m) to build the bridge tree and O(C log C) to preprocess LCA; each query runs in O(log C), where C is the number of 2-edge-connected components.Space: O(n + m) for the graph, O(C log C) for binary lifting tables.
Count Marked (Must-Use) Bridges on a Path Using Prefix Sums on the Bridge Tree
1#include <bits/stdc++.h>
2using namespace std;
3
4struct Edge { int u, v; };
5
6int main(){
7    ios::sync_with_stdio(false);
8    cin.tie(nullptr);
9
10    int n, m; cin >> n >> m;
11    vector<Edge> edges(m);
12    vector<vector<pair<int,int>>> adj(n+1);
13    for (int i = 0; i < m; ++i) {
14        int u, v; cin >> u >> v;
15        edges[i] = {u, v};
16        adj[u].push_back({v, i});
17        adj[v].push_back({u, i});
18    }
19
20    // Bridges via Tarjan
21    vector<int> tin(n+1, -1), low(n+1, -1);
22    vector<char> vis(n+1,false), isBridge(m,false);
23    int timer = 0;
24    function<void(int,int)> dfs = [&](int u, int peid){
25        vis[u] = true; tin[u] = low[u] = timer++;
26        for (auto [v, eid] : adj[u]){
27            if (eid == peid) continue;
28            if (vis[v]) low[u] = min(low[u], tin[v]);
29            else {
30                dfs(v, eid);
31                low[u] = min(low[u], low[v]);
32                if (low[v] > tin[u]) isBridge[eid] = true;
33            }
34        }
35    };
36    for (int i = 1; i <= n; ++i) if (!vis[i]) dfs(i, -1);
37
38    // 2ECCs (ignore bridges)
39    vector<int> comp(n+1, -1); int C = 0;
40    function<void(int)> paint = [&](int s){
41        stack<int> st; st.push(s); comp[s] = C;
42        while(!st.empty()){
43            int u = st.top(); st.pop();
44            for (auto [v, eid] : adj[u]){
45                if (isBridge[eid]) continue;
46                if (comp[v] == -1){ comp[v] = C; st.push(v); }
47            }
48        }
49    };
50    for (int i = 1; i <= n; ++i) if (comp[i] == -1){ paint(i); ++C; }
51
52    // Build weighted bridge tree: weight 1 if bridge is marked 'must-use', else 0
53    int k; cin >> k; // number of marked edges by ID or endpoints? We'll read IDs for clarity.
54    vector<char> marked(m, false);
55    for (int i = 0; i < k; ++i){
56        int eid; cin >> eid; // assume 0-based edge IDs provided by input
57        if (0 <= eid && eid < m) marked[eid] = true;
58    }
59
60    vector<vector<pair<int,int>>> tree(C); // (to, weight)
61    for (int eid = 0; eid < m; ++eid) if (isBridge[eid]){
62        int a = comp[edges[eid].u], b = comp[edges[eid].v];
63        int w = marked[eid] ? 1 : 0; // only bridges can contribute
64        tree[a].push_back({b, w});
65        tree[b].push_back({a, w});
66    }
67
68    // LCA + prefix sums of weights to count marked bridges on any path
69    int LOG = 1; while ((1<<LOG) <= max(1,C)) ++LOG;
70    vector<vector<int>> up(LOG, vector<int>(C, -1));
71    vector<int> depth(C, 0), rootOf(C, -1), pref(C, 0); // pref: sum of weights from root to node
72
73    function<void(int,int,int)> dfsTree = [&](int u, int p, int r){
74        up[0][u] = (p == -1 ? u : p);
75        rootOf[u] = r;
76        for (int j = 1; j < LOG; ++j) up[j][u] = up[j-1][ up[j-1][u] ];
77        for (auto [v, w] : tree[u]) if (v != p){
78            depth[v] = depth[u] + 1;
79            pref[v] = pref[u] + w; // accumulate marked bridges along the parent edge
80            dfsTree(v, u, r);
81        }
82    };
83    for (int i = 0; i < C; ++i) if (rootOf[i] == -1) dfsTree(i, -1, i);
84
85    auto lca = [&](int a, int b){
86        if (rootOf[a] != rootOf[b]) return -1;
87        if (depth[a] < depth[b]) swap(a,b);
88        int k = depth[a] - depth[b];
89        for (int j = LOG-1; j >= 0; --j) if (k & (1<<j)) a = up[j][a];
90        if (a == b) return a;
91        for (int j = LOG-1; j >= 0; --j) if (up[j][a] != up[j][b]){ a = up[j][a]; b = up[j][b]; }
92        return up[0][a];
93    };
94
95    auto countMarkedOnPath = [&](int a, int b){
96        int c = lca(a,b);
97        if (c == -1) return -1; // disconnected
98        // sum along path = pref[a] + pref[b] - 2*pref[c]
99        return pref[a] + pref[b] - 2*pref[c];
100    };
101
102    int q; cin >> q;
103    while (q--) {
104        int u, v; cin >> u >> v; // original vertices
105        int a = comp[u], b = comp[v];
106        int ans = countMarkedOnPath(a, b);
107        cout << ans << '\n'; // -1 if disconnected; otherwise number of marked bridges
108    }
109
110    return 0;
111}
112

This program counts how many pre-marked bridges lie on the path between two original vertices. It builds the bridge tree and stores a prefix sum pref[x] of edge weights (1 for marked bridges, 0 otherwise) from the root to each node. The number of marked bridges between comp(u) and comp(v) is pref[a] + pref[b] − 2·pref[lca(a,b)].

Time: O(n + m) to build; O(C log C) preprocessing; O(log C) per query.Space: O(n + m) for graph and bridge structures; O(C log C) for LCA tables; O(C) for prefix sums.