Critical Connections in a Network

LeetCode 1192: Critical Connections in a Network Solution & Explanation

Problem Overview

TL;DR: The optimal solution utilizes Tarjan's bridge-finding algorithm (a variation of DFS) to identify edges that are not part of any cycle by tracking discovery times and low-link values in $O(V+E)$ time.

The problem asks us to identify all "critical connections" in a network of servers. We are given n servers and a list of undirected connections. A critical connection is defined as an edge that, if removed, would increase the number of connected components in the graph (i.e., disconnect the network). In graph theory, these edges are formally known as bridges.

This is a classic application of Depth-First Search (DFS) on an undirected graph. The goal of the LeetCode 1192 solution is to efficiently find all bridges without repeatedly traversing the graph.

Brute Force Approach for Critical Connections in a Network

A naive approach to finding critical connections involves testing every edge individually to see if its removal disconnects the graph.

1. Iterate through every connection [u, v] in the connections list.
2. Temporarily remove the edge [u, v] from the graph.
3. Perform a traversal (BFS or DFS) starting from an arbitrary node to count the number of reachable nodes.
4. If the number of reachable nodes is less than n, the graph is disconnected. Therefore, [u, v] is a critical connection.
5. Add the edge back to the graph and proceed to the next connection.

Pseudo-code:

function findCriticalConnections(n, connections):
    result = []
    for each edge (u, v) in connections:
        remove (u, v) from graph
        count = BFS_count_reachable_nodes(start_node=0)
        if count < n:
            result.add([u, v])
        add (u, v) back to graph
    return result

Complexity Analysis: The time complexity of a single BFS/DFS is $O(V + E)$. Since we repeat this for every edge $E$, the total time complexity is $O(E \times (V + E))$. Given the constraints where $n \le 10^5$ and edges can be up to $10^5$, this results in roughly $10^{10}$ operations, which will inevitably result in a Time Limit Exceeded (TLE) error.

Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)

We implement Tarjan's algorithm using the following strategy:

1. Graph Construction: Build an adjacency list from the input connections.
2. State Initialization:
   • ids array initialized to -1 (unvisited).
   • low array to track the lowest reachable timestamp.
   • A global timer starting at 0.
3. DFS Traversal:
   • Start DFS from node 0 (since the graph is connected).
   • For each node u, set ids[u] and low[u] to the current timer, then increment the timer.
   • Iterate through neighbors v of u.
4. Handling Neighbors:
   • Case 1: v is the parent of u: Ignore this edge to avoid trivial cycles (immediate backtrack).
   • Case 2: v is already visited: This is a back-edge. Update low[u] to be the minimum of low[u] and ids[v]. This indicates u is part of a cycle connecting back to v.
   • Case 3: v is unvisited: Recursively call DFS on v. After the call returns, update low[u] = min(low[u], low[v]) to propagate the lowest reachable ID from the child.
5. Bridge Identification:
   • After returning from the recursive call to v, check if low[v] > ids[u].
   • If true, add [u, v] to the results list.

Execution Flow

1. Setup: We convert the edge list [[0,1],[1,2],[2,0],[1,3]] into an adjacency list: 0:[1,2], 1:[0,2,3], 2:[1,0], 3:[1].
2. Start DFS(0):
   • Set id[0]=0, low[0]=0. Timer becomes 1.
3. Visit Neighbor 1:
   • id[1]=1, low[1]=1. Timer becomes 2.
   • From 1, Visit Neighbor 2:
     • id[2]=2, low[2]=2. Timer becomes 3.
     • From 2, Visit Neighbor 0:
       • Node 0 is visited. It is not 2's parent (which is 1).
       • Update low[2] = min(low[2], id[0]) -> low[2] = 0.
     • From 2, Visit Neighbor 1:
       • Node 1 is the parent of 2. Ignore.
     • DFS(2) Returns: low[2] is 0.
   • Back in DFS(1): Update low[1] = min(low[1], low[2]) -> low[1] = 0.
   • Check Bridge: Is low[2] (0) > id[1] (1)? False. Edge (1,2) is not critical.
   • From 1, Visit Neighbor 3:
     • id[3]=3, low[3]=3. Timer becomes 4.
     • From 3, Visit Neighbor 1:
       • Node 1 is parent. Ignore.
     • DFS(3) Returns: low[3] is 3.
   • Back in DFS(1): Update low[1] = min(low[1], low[3]) -> low[1] remains 0.
   • Check Bridge: Is low[3] (3) > id[1] (1)? True.
   • Result: Add [1, 3] to critical connections.
4. DFS(1) Returns: low[1] is 0.
5. Back in DFS(0): Update low[0] = min(low[0], low[1]) -> low[0] = 0.
6. End: Return result [[1, 3]].

Proof of Correctness

The algorithm correctly identifies all bridges because of the relationship between discovery times and low-link values.

The value low[v] represents the smallest discovery time reachable from the subtree rooted at v (in the DFS tree) using only tree edges within the subtree and at most one back-edge out of the subtree.

If low[v] <= ids[u] (where $u$ is the parent of $v$), it proves there is a path from $v$ back to $u$ or an ancestor of $u$ that does not involve the direct edge $(u, v)$. This forms a cycle, meaning removing $(u, v)$ does not disconnect $v$ from the rest of the graph.

Conversely, if low[v] > ids[u], it strictly implies that no node in $v$'s subtree has a back-edge to $u$ or any node discovered before $u$. Thus, the only path from the component containing $u$ to the component containing $v$ is the edge $(u, v)$. Removing it disconnects the graph.

Pattern Reuse Notes

The pattern Graph - Bridges & Articulation Points (Tarjan low-link) is a specialized form of DFS used in advanced graph connectivity problems.

• LeetCode 1489: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
  • This problem requires finding bridges in a subgraph formed by MST candidate edges. The core logic of identifying critical edges via bridge finding remains the same.

Reference Implementation

C++ Solution for LeetCode 1192

1class Solution {
2private:
3    vector<vector<int>> adj;
4    vector<int> ids;
5    vector<int> low;
6    vector<vector<int>> bridges;
7    int timer;
8
9    void dfs(int current, int parent) {
10        ids[current] = low[current] = ++timer;
11
12        for (int neighbor : adj[current]) {
13            if (neighbor == parent) {
14                continue; // Don't go back along the tree edge
15            }
16
17            if (ids[neighbor] != -1) {
18                // Back-edge detected
19                low[current] = min(low[current], ids[neighbor]);
20            } else {
21                // Tree-edge
22                dfs(neighbor, current);
23                low[current] = min(low[current], low[neighbor]);
24                
25                // Check if the edge is a bridge
26                if (low[neighbor] > ids[current]) {
27                    bridges.push_back({current, neighbor});
28                }
29            }
30        }
31    }
32
33public:
34    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
35        adj.assign(n, vector<int>());
36        ids.assign(n, -1);
37        low.assign(n, -1);
38        bridges.clear();
39        timer = 0;
40
41        // Build Graph
42        for (const auto& conn : connections) {
43            adj[conn[0]].push_back(conn[1]);
44            adj[conn[1]].push_back(conn[0]);
45        }
46
47        // Run DFS (Graph is connected, so start from 0 covers all)
48        dfs(0, -1);
49
50        return bridges;
51    }
52};

Java Solution for LeetCode 1192

1import java.util.*;
2
3class Solution {
4    private List<List<Integer>> adj;
5    private int[] ids;
6    private int[] low;
7    private List<List<Integer>> bridges;
8    private int timer;
9
10    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
11        adj = new ArrayList<>();
12        bridges = new ArrayList<>();
13        ids = new int[n];
14        low = new int[n];
15        Arrays.fill(ids, -1);
16        timer = 0;
17
18        for (int i = 0; i < n; i++) {
19            adj.add(new ArrayList<>());
20        }
21
22        for (List<Integer> conn : connections) {
23            int u = conn.get(0);
24            int v = conn.get(1);
25            adj.get(u).add(v);
26            adj.get(v).add(u);
27        }
28
29        dfs(0, -1);
30
31        return bridges;
32    }
33
34    private void dfs(int current, int parent) {
35        ids[current] = low[current] = ++timer;
36
37        for (int neighbor : adj.get(current)) {
38            if (neighbor == parent) {
39                continue;
40            }
41
42            if (ids[neighbor] != -1) {
43                // Back-edge
44                low[current] = Math.min(low[current], ids[neighbor]);
45            } else {
46                // Tree-edge
47                dfs(neighbor, current);
48                low[current] = Math.min(low[current], low[neighbor]);
49                
50                if (low[neighbor] > ids[current]) {
51                    bridges.add(Arrays.asList(current, neighbor));
52                }
53            }
54        }
55    }
56}

Python Solution for LeetCode 1192

1import sys
2
3# Increase recursion depth for deep graphs
4sys.setrecursionlimit(200000)
5
6class Solution:
7    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
8        adj = [[] for _ in range(n)]
9        for u, v in connections:
10            adj[u].append(v)
11            adj[v].append(u)
12            
13        ids = [-1] * n
14        low = [-1] * n
15        bridges = []
16        self.timer = 0
17        
18        def dfs(current, parent):
19            self.timer += 1
20            ids[current] = low[current] = self.timer
21            
22            for neighbor in adj[current]:
23                if neighbor == parent:
24                    continue
25                
26                if ids[neighbor] != -1:
27                    # Back-edge
28                    low[current] = min(low[current], ids[neighbor])
29                else:
30                    # Tree-edge
31                    dfs(neighbor, current)
32                    low[current] = min(low[current], low[neighbor])
33                    
34                    if low[neighbor] > ids[current]:
35                        bridges.append([current, neighbor])
36        
37        dfs(0, -1)
38        return bridges