G-55. Bridges in Graph - Using Tarjan's Algorithm of Time In and Low Time

Finding bridges in a graph is a fundamental graph theory problem with critical real-world applications in network reliability, circuit design, and distributed systems. This chapter explores Tarjan's Algorithm using time-in and low-time tracking during a Depth First Search (DFS) traversal to identify bridges efficiently.

1. Why Do We Need This? (Problem Statement & Status Quo)

In network design, routing, or infrastructure planning, identifying single points of failure is paramount.

• The Status Quo: Checking every single edge by removing it, running a connectivity algorithm (like BFS or DFS) to see if the graph splits, and then restoring it is computationally expensive. For a graph with $E$ edges, a naive removal approach results in an unacceptable $O(E \times (V + E))$ time complexity.
• The Problem: We need an optimal, single-traversal approach to locate all edges whose removal disconnects the graph into two or more independent components.

2. Core Definition: What is a Bridge?

A Bridge (or cut-edge) in a connected graph is an edge whose removal increases the number of connected components in the graph.

• If removed: The graph splits into 2 or more standalone sub-graphs.
• If not a bridge: Removing the edge still leaves all endpoints connected via an alternative path (forming a cycle).

3. Core Mental Model & The Two-Array Strategy

To find bridges efficiently during a single DFS traversal, we maintain two tracking arrays for every node:

1. Time of Insertion (tin or timeIn): Records the exact step or timer count when a node is first reached during the DFS traversal.
2. Lowest Time of Insertion (low): Records the lowest tin reachable from the current node using at most one back-edge, with one strict rule: we never consider the edge leading back to the parent.

Real-Life Analogy: The Corporate Auditor

Imagine an auditor (the DFS traversal) moving down a corporate hierarchy (the graph).

• As the auditor visits each department, they stamp the arrival time (tin).
• When the auditor reaches the bottom of a branch, they look around to see if any backdoor or alternative communication channel exists connecting back to an upper-level department (apart from the direct supervisor who brought them here).
• If a backdoor exists, the department's lowest reachable time (low) drops. If no backdoor exists, the low time equals the arrival time, meaning cutting that link isolates the department completely.

4. Step-by-Step Algorithm Mechanics

During the DFS traversal:

1. Mark the current node as visited and set tin[node] = low[node] = timer, then increment the global timer.
2. Iterate through all adjacent nodes:
   • Case 1: Adjacent node is the parent. Skip it immediately. We do not evaluate back-edges through our direct parent.
   • Case 2: Adjacent node is already visited. This is a back-edge. Update our current node's low time: low[node] = min(low[node], tin[adj]).
   • Case 3: Adjacent node is unvisited. Recursively call DFS on the adjacent node. Upon return, update our current node's low time: low[node] = min(low[node], low[adj]).
3. Bridge Condition Check: After returning from an adjacent node, check if the adjacent node's lowest reachable time can bypass the current node:

If true, the edge (node $\leftrightarrow$ adj) is a bridge! Why? Because the subtree rooted at adj has no alternative path back to node or any of its ancestors.

5. Dry Run Walkthrough

Consider a graph where we perform DFS starting from node 1.

• We traverse down the chain: 1 -> 2 -> 3 -> 4 -> 5 -> 6.
• At node 6, it connects back to node 5 (already visited).
• When backtracking from 6 to 5, 5 checks: low[6] ($5$) is not strictly greater than tin[5] ($5$). Thus, edge (5, 6) is not a bridge because node 6 can reach back to 5.
• Conversely, consider edge (8, 10) in a branched section:
  • tin[8] = 8, low[8] = 6 (via another path).
  • tin[10] = 10, low[10] = 10.
  • When returning from 10, low[10] ($10$) $>$ tin[8] ($8$).
  • Because the subtree at 10 cannot reach back to 8 or above, (8, 10) is identified as a bridge.

6. Comprehensive Flow Walkthrough

The recursive DFS state transition for bridge detection follows this vertical flow:

7. Tabular Synthesis: Algorithm Variables & States

8. C++ Implementation

Below is the complete, production-grade C++ implementation demonstrating Tarjan's Bridge-Finding algorithm:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
private:
    int timer = 1;

    void dfs(int node, int parent, vector<int>& vis, vector<int>& tin, 
             vector<int>& low, vector<vector<int>>& adj, vector<vector<int>>& bridges) {
        
        vis[node] = 1;
        tin[node] = low[node] = timer;
        timer++;

        for (auto it : adj[node]) {
            if (it == parent) continue; // Skip parent edge

            if (!vis[it]) {
                // If neighbor is not visited, traverse down its subtree
                dfs(it, node, vis, tin, low, adj, bridges);

                // Upon return, update low time greedily
                low[node] = min(low[node], low[it]);

                // Bridge condition check
                if (low[it] > tin[node]) {
                    bridges.push_back({node, it});
                }
            } else {
                // Back-edge found: update low time with neighbor's insertion time
                low[node] = min(low[node], tin[it]);
            }
        }
    }

public:
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        // Step 1: Build adjacency list
        vector<vector<int>> adj(n);
        for (auto it : connections) {
            adj[it[0]].push_back(it[1]);
            adj[it[1]].push_back(it[0]);
        }

        vector<int> vis(n, 0);
        vector<int> tin(n, 0);
        vector<int> low(n, 0);
        vector<vector<int>> bridges;

        // Step 2: Run DFS from node 0 (assuming 0-indexed, connected graph)
        dfs(0, -1, vis, tin, low, adj, bridges);

        return bridges;
    }
};

9. Complexity Analysis

• Time Complexity: $\mathcal{O}(V + 2E)$
  • Building the adjacency list takes $\mathcal{O}(V + E)$.
  • The DFS traversal visits every node once ($\mathcal{O}(V)$) and explores every edge twice in an undirected graph ($\mathcal{O}(2E)$). Thus, linear time efficiency.
• Space Complexity: $\mathcal{O}(V + E)$
  • Adjacency list storage: $\mathcal{O}(V + 2E)$.
  • Recursion stack space (in the worst-case linear graph): $\mathcal{O}(V)$.
  • Auxiliary arrays (vis, tin, low): $\mathcal{O}(V)$.

Summary and Key Takeaways

• Definition of a Bridge: An edge whose removal breaks a single connected component into two or more independent sub-components.
• Prerequisite: A solid understanding of standard Depth First Search (DFS) traversal.
• Dual-Array Tracking: Tarjan's algorithm relies on two metrics per node: tin (time of insertion) and low (lowest insertion time reachable).
• The Parent Exclusion Rule: When checking adjacent nodes, always ignore the edge leading back to the parent to prevent false cycle assumptions.
• The Bridge Condition: An edge from node to adj is a bridge if and only if low[adj] > tin[node].
• Efficiency: Running in $\mathcal{O}(V + 2E)$ time, Tarjan's algorithm avoids the prohibitive overhead of naive edge-removal approaches.