Bridges in Graph Tarjan's Algorithm in DSA C++

Mental Model

A bridge is an edge that, if removed, increases the number of disconnected parts in a graph. Tarjan's algorithm finds these by exploring nodes deeply and tracking the earliest reachable node from each subtree.

Analogy: Imagine a city connected by roads. A bridge is a road that, if closed, splits the city into two parts with no way to travel between them. Tarjan's algorithm is like a detective checking each road and seeing if there's an alternative route to avoid breaking the city apart.

Graph nodes connected by edges:
  1 --- 2
   \   |
    \  |
      3

Pointers:
  disc[]: discovery time of each node
  low[]: earliest visited node reachable
  DFS tree edges and back edges shown by arrows

Dry Run Walkthrough

Input: Graph with edges: 1-2, 2-3, 3-1, 2-4

Goal: Find all bridges in the graph, edges that if removed increase disconnected parts

Step 1: Start DFS from node 1, set discovery time and low to 1

disc[1]=1, low[1]=1
Visited nodes: 1
Stack: []

Why: Initialize discovery and low values for node 1 to track earliest reachable node

Step 2: Move to node 2 from node 1, set disc[2]=2, low[2]=2

disc[1]=1, low[1]=1
 disc[2]=2, low[2]=2
Visited nodes: 1,2

Why: Explore neighbor node 2 and assign discovery and low times

Step 3: Move to node 3 from node 2, set disc[3]=3, low[3]=3

disc[1]=1, low[1]=1
 disc[2]=2, low[2]=2
 disc[3]=3, low[3]=3
Visited nodes: 1,2,3

Why: Explore neighbor node 3 and assign discovery and low times

Step 4: Node 3 sees back edge to node 1, update low[3] = min(low[3], disc[1]) = 1

disc[1]=1, low[1]=1
 disc[2]=2, low[2]=2
 disc[3]=3, low[3]=1

Why: Back edge shows node 3 can reach node 1 earlier, update low to reflect this

Step 5: Backtrack to node 2, update low[2] = min(low[2], low[3]) = 1

disc[1]=1, low[1]=1
 disc[2]=2, low[2]=1
 disc[3]=3, low[3]=1

Why: Node 2 updates low based on subtree rooted at 3

Step 6: From node 2, move to node 4, set disc[4]=4, low[4]=4

disc[1]=1, low[1]=1
 disc[2]=2, low[2]=1
 disc[3]=3, low[3]=1
 disc[4]=4, low[4]=4

Why: Explore new node 4 and assign discovery and low times

Step 7: Node 4 has no unvisited neighbors, backtrack to node 2, update low[2] = min(low[2], low[4]) = 1

disc[1]=1, low[1]=1
 disc[2]=2, low[2]=1
 disc[3]=3, low[3]=1
 disc[4]=4, low[4]=4

Why: Update low of node 2 considering subtree rooted at 4

Step 8: Check edge 2-4: since low[4] > disc[2], edge 2-4 is a bridge

Bridge found: edge 2-4

Why: If low of child is greater than discovery of parent, edge is a bridge

Result:

Bridge edges: 2-4

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Graph {
public:
    int V;
    vector<vector<int>> adj;
    Graph(int V) {
        this->V = V;
        adj.resize(V + 1);
    }
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    void bridgeUtil(int u, vector<bool> &visited, vector<int> &disc, vector<int> &low, int &time, int parent, vector<pair<int,int>> &bridges) {
        visited[u] = true;
        disc[u] = low[u] = ++time; // discovery and low time

        for (int v : adj[u]) {
            if (!visited[v]) {
                bridgeUtil(v, visited, disc, low, time, u, bridges); // DFS
                low[u] = min(low[u], low[v]); // update low[u]

                if (low[v] > disc[u]) {
                    bridges.push_back({u, v}); // found bridge
                }
            } else if (v != parent) {
                low[u] = min(low[u], disc[v]); // back edge
            }
        }
    }
    vector<pair<int,int>> findBridges() {
        vector<bool> visited(V + 1, false);
        vector<int> disc(V + 1, -1);
        vector<int> low(V + 1, -1);
        vector<pair<int,int>> bridges;
        int time = 0;

        for (int i = 1; i <= V; i++) {
            if (!visited[i]) {
                bridgeUtil(i, visited, disc, low, time, -1, bridges);
            }
        }
        return bridges;
    }
};

int main() {
    Graph g(4);
    g.addEdge(1, 2);
    g.addEdge(2, 3);
    g.addEdge(3, 1);
    g.addEdge(2, 4);

    vector<pair<int,int>> bridges = g.findBridges();
    for (auto &edge : bridges) {
        cout << edge.first << " - " << edge.second << "\n";
    }
    return 0;
}

disc[u] = low[u] = ++time; // discovery and low time

Assign discovery and low time when visiting node u

bridgeUtil(v, visited, disc, low, time, u, bridges); // DFS

Recursively visit unvisited neighbor v

low[u] = min(low[u], low[v]); // update low[u]

Update low[u] based on child's low value

if (low[v] > disc[u]) { bridges.push_back({u, v}); }

If child's low is greater than discovery of u, edge u-v is a bridge

else if (v != parent) { low[u] = min(low[u], disc[v]); }

Update low[u] for back edges to ancestors

Output

2 - 4

Complexity Analysis

Time: O(V + E) because each vertex and edge is visited once during DFS

Space: O(V) for storing discovery, low arrays, visited flags, and recursion stack

vs Alternative: Naive approach checks connectivity after removing each edge, costing O(V*(V+E)) which is much slower

Edge Cases

Graph with no edges

No bridges found because no edges exist

DSA C++

for (int i = 1; i <= V; i++) { if (!visited[i]) { bridgeUtil(...); } }

Graph with a single node

No bridges found because no edges exist

DSA C++

for (int i = 1; i <= V; i++) { if (!visited[i]) { bridgeUtil(...); } }

Graph with multiple disconnected components

Algorithm runs DFS on each component to find bridges in all parts

DSA C++

for (int i = 1; i <= V; i++) { if (!visited[i]) { bridgeUtil(...); } }

When to Use This Pattern

When asked to find edges whose removal disconnects the graph, use Tarjan's bridge-finding algorithm because it efficiently finds all such edges in one DFS pass.

Common Mistakes

Mistake: Not updating low[u] for back edges to ancestors
Fix: Add else if (v != parent) condition to update low[u] with disc[v]

Mistake: Comparing low[v] >= disc[u] instead of low[v] > disc[u]
Fix: Use strict greater than to correctly identify bridges

Mistake: Not initializing discovery and low arrays properly
Fix: Initialize disc and low with -1 and update on first visit

Summary

Finds edges in a graph that, if removed, increase disconnected parts (bridges).

Use when you need to identify critical connections in networks or graphs.

The key insight is tracking earliest reachable nodes using discovery and low times during DFS.

Practice

1. What is the main purpose of Tarjan's algorithm when finding bridges in a graph?

easy

A. To detect cycles in a graph

B. To find the shortest path between two nodes

C. To find edges that, if removed, increase the number of connected components

D. To count the total number of edges in the graph

Solution

1. Step 1: Understand the definition of a bridge

   A bridge is an edge that, when removed, increases the number of connected components in the graph.

2. Step 2: Relate Tarjan's algorithm to bridges

   Tarjan's algorithm efficiently finds such edges by using DFS and tracking discovery and low times.

3. Final Answer:

   To find edges that, if removed, increase the number of connected components -> Option C

4. Quick Check:

   Bridges = edges increasing components when removed [OK]

Hint: Bridges disconnect graph if removed [OK]

Common Mistakes:

• Confusing bridges with cycles
• Thinking it finds shortest paths
• Assuming it counts edges only

2. Which of the following is the correct way to declare the discovery time array in C++ for Tarjan's bridge-finding algorithm on a graph with n vertices?

easy

A. int disc[n];

B. vector<int> disc(n, -1);

C. int disc = new int[n];

D. int disc[] = new int();

Solution

1. Step 1: Understand C++ array and vector declarations

   Static arrays like int disc[n]; are not standard in C++ (unless n is a constant). Using vector<int> is safer and dynamic.

2. Step 2: Identify correct initialization for discovery times

   Initializing with -1 indicates unvisited nodes, which is common practice.

3. Final Answer:

   vector<int> disc(n, -1); -> Option B

4. Quick Check:

   Use vector with size and initial value [OK]

Hint: Use vector<int> with size and init value [OK]

Common Mistakes:

• Using variable-length arrays (not standard C++)
• Incorrect pointer syntax
• Not initializing discovery times

3. Consider the following C++ code snippet using Tarjan's algorithm to find bridges. What will be the output bridges for the given graph edges?

int n = 4;
vector<int> graph[4];
graph[0].push_back(1);
graph[1].push_back(0);
graph[1].push_back(2);
graph[2].push_back(1);
graph[2].push_back(3);
graph[3].push_back(2);
// After running Tarjan's bridge finder, which edges are bridges?
// Edges are represented as pairs (u, v) with u < v

medium

A. [(0, 1), (1, 2), (2, 3)]

B. [(0, 1), (1, 2)]

C. [(0, 1), (2, 3)]

D. []

Solution

1. Step 1: Visualize the graph structure

   The graph is a chain: 0 - 1 - 2 - 3 with bidirectional edges, forming a path with no cycles.

2. Step 2: Apply Tarjan's bridge finding logic

   In a path graph (a tree), every edge is a bridge because removing any disconnects the graph. Tarjan's DFS will detect all three edges where low[v] > disc[u] for each tree edge.

3. Final Answer:

   [(0, 1), (1, 2), (2, 3)] -> Option A

4. Quick Check:

   All edges in path are bridges [OK]

Hint: All edges in chain are bridges [OK]

Common Mistakes:

• Ignoring edge (0,1) as a bridge
• Assuming no bridges in chain
• Confusing bridge with cycle edges

4. Identify the bug in the following Tarjan's algorithm snippet for finding bridges:

void dfs(int u, int parent) {
  visited[u] = true;
  disc[u] = low[u] = time++;
  for (int v : graph[u]) {
    if (v == parent) continue;
    if (!visited[v]) {
      dfs(v, u);
      low[u] = min(low[u], low[v]);
      if (low[v] > disc[u])
        bridges.push_back({u, v});
    } else {
      low[u] = min(low[u], disc[v]);
    }
  }
}

medium

A. Missing initialization of time variable before DFS

B. Incorrect comparison in if condition for bridge detection

C. Not marking nodes as visited

D. Not checking for parent node in adjacency

Solution

1. Step 1: Review the DFS function variables

   The variable 'time' is used to assign discovery times but is not shown initialized before DFS calls.

2. Step 2: Understand impact of uninitialized time

   If 'time' is not initialized to 0 before DFS, discovery and low times will be incorrect, causing wrong bridge detection.

3. Final Answer:

   Missing initialization of time variable before DFS -> Option A

4. Quick Check:

   Initialize time = 0 before DFS [OK]

Hint: Initialize time counter before DFS call [OK]

Common Mistakes:

• Forgetting to initialize time
• Confusing low and disc arrays
• Not skipping parent node in DFS

5. Given a connected undirected graph with n vertices and m edges, how can Tarjan's algorithm be adapted to find all bridges efficiently, and what is its time complexity?

hard

A. Use Dijkstra's algorithm; time complexity O(m log n)

B. Use BFS with distance arrays; time complexity O(n^2)

C. Use DFS without low arrays; time complexity O(m^2)

D. Use DFS with discovery and low arrays; time complexity O(n + m)

Solution

1. Step 1: Describe Tarjan's algorithm adaptation

   Tarjan's algorithm uses DFS traversal, tracking discovery times and low values to detect bridges efficiently.

2. Step 2: Analyze time complexity

   Each vertex and edge is visited once during DFS, so the time complexity is O(n + m), where n is vertices and m is edges.

3. Final Answer:

   Use DFS with discovery and low arrays; time complexity O(n + m) -> Option D

4. Quick Check:

   DFS + low arrays = O(n + m) [OK]

Hint: DFS with low arrays runs in linear time [OK]

Common Mistakes:

• Using BFS which is not suitable here
• Ignoring low arrays in DFS
• Confusing with shortest path algorithms