LeetCode 1192 - Critical Connections in a Network

This problem gives us an undirected graph representing a network of servers. Each server is identified by an integer from 0 to n - 1, and each pair [a, b] in connections represents a bidirectional edge between server a and server b.

leetcodeharddepth-first-searchgraph-theorybiconnected-component

LeetCode Problem 1192

Difficulty: 🔴 Hard
Topics: Depth-First Search, Graph Theory, Biconnected Component

Solution

LeetCode 1192 - Critical Connections in a Network

Problem Understanding

This problem gives us an undirected graph representing a network of servers. Each server is identified by an integer from 0 to n - 1, and each pair [a, b] in connections represents a bidirectional edge between server a and server b.

The graph is connected, meaning every server can reach every other server through some path. Our goal is to identify all critical connections.

A connection is considered critical if removing that edge disconnects part of the network. In graph theory, such an edge is called a bridge. If deleting an edge increases the number of connected components in the graph, then that edge is a bridge.

For example, consider this graph:

0 --- 1 --- 3
 \   /
   2

The triangle formed by 0, 1, and 2 has redundant paths. Removing any edge inside the triangle still leaves those nodes connected through another route. However, node 3 is connected only through edge [1,3]. Removing that edge isolates node 3, so [1,3] is a critical connection.

The constraints are important:

  • n can be as large as 10^5
  • The number of edges can also be as large as 10^5

These limits immediately rule out expensive graph recomputation approaches. Any algorithm worse than roughly O(n + m) where m is the number of edges will likely time out.

The graph has several guarantees:

  • No self loops
  • No duplicate edges
  • The graph is connected

These guarantees simplify implementation because we do not need to handle disconnected components or repeated adjacency entries.

Several edge cases are important:

  • A graph with only two nodes and one edge, that edge is always critical.
  • A graph containing cycles, edges inside cycles are never critical because alternate paths exist.
  • A tree structure, every edge is critical because removing any edge disconnects the graph.
  • Dense cyclic regions connected by narrow bridges, only the bridge edges should be returned.

Approaches

Brute Force Approach

The brute force approach is straightforward conceptually.

For every edge in the graph:

  1. Temporarily remove the edge.
  2. Run a DFS or BFS from any node.
  3. Check whether all nodes are still reachable.
  4. If not, the removed edge is critical.
  5. Restore the edge and continue.

This works because the definition of a critical connection is exactly whether the graph becomes disconnected after removing that edge.

However, the performance is very poor.

Suppose there are m edges. For each edge, we perform a graph traversal costing O(n + m). Therefore the total complexity becomes:

O(m × (n + m))

With both n and m up to 10^5, this is far too slow.

Optimal Approach, Tarjan's Bridge Algorithm

The key insight is that we do not need to recompute connectivity for every edge independently.

Instead, we can analyze the graph during a single DFS traversal.

The important observation is this:

If a node can reach one of its ancestors through a back edge, then the edge leading into that node is not critical because an alternate path exists.

To capture this efficiently, we maintain two values for every node:

  • discovery[node]

  • The DFS visitation order when the node is first seen.

  • low[node]

  • The earliest discovery time reachable from that node or its descendants using at most one back edge.

If during DFS we traverse:

u -> v

and later determine:

low[v] > discovery[u]

then there is no alternate route from v or its subtree back to u or any ancestor of u.

That means edge [u,v] is a bridge, therefore it is a critical connection.

This algorithm is known as Tarjan's bridge finding algorithm and runs in linear time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(m × (n + m)) O(n + m) Remove each edge and test connectivity
Optimal O(n + m) O(n + m) Single DFS using discovery and low-link values

Algorithm Walkthrough

Step 1: Build the adjacency list

Since the graph is undirected, every edge [u,v] is added in both directions.

We use an adjacency list because it provides efficient traversal and uses memory proportional to the number of edges.

Step 2: Initialize DFS bookkeeping arrays

We maintain:

  • discovery[node]

  • Stores when a node was first visited.

  • Initialized to -1 for unvisited nodes.

  • low[node]

  • Stores the earliest reachable discovery time.

We also maintain a global time counter that increases whenever a node is first visited.

Step 3: Start DFS traversal

We begin DFS from node 0.

During DFS:

  • Mark the node with the current timestamp.
  • Set both discovery[node] and low[node] initially to the same value.
  • Explore all neighbors.

Step 4: Skip the parent edge

In an undirected graph, every edge appears twice.

When traversing from u to v, we do not want to immediately revisit u from v and mistakenly treat it as a back edge.

Therefore we skip the neighbor if it is the DFS parent.

Step 5: Handle unvisited neighbors

If neighbor v has not been visited:

  1. Recurse into v
  2. After recursion returns:
  • Update:
low[u] = min(low[u], low[v])

This propagates the earliest reachable ancestor upward.

Step 6: Detect bridges

After processing child v, check:

low[v] > discovery[u]

If true:

  • v cannot reach u or any ancestor of u
  • Removing edge [u,v] disconnects the graph

Therefore [u,v] is a critical connection.

Step 7: Handle back edges

If neighbor v is already visited and is not the parent:

low[u] = min(low[u], discovery[v])

This means u found a path back to an earlier ancestor.

Why it works

The algorithm works because low[node] precisely captures the earliest ancestor reachable from that node's DFS subtree.

If a subtree rooted at v cannot reach any ancestor of u, then the only connection between that subtree and the rest of the graph is edge [u,v].

Therefore removing that edge disconnects the graph, making it a bridge.

Conversely, if a back edge exists, then an alternate route exists and the edge is not critical.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = defaultdict(list)

        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)

        discovery = [-1] * n
        low = [-1] * n
        time = 0
        bridges = []

        def dfs(node: int, parent: int) -> None:
            nonlocal time

            discovery[node] = time
            low[node] = time
            time += 1

            for neighbor in graph[node]:
                if neighbor == parent:
                    continue

                if discovery[neighbor] == -1:
                    dfs(neighbor, node)

                    low[node] = min(low[node], low[neighbor])

                    if low[neighbor] > discovery[node]:
                        bridges.append([node, neighbor])
                else:
                    low[node] = min(low[node], discovery[neighbor])

        dfs(0, -1)

        return bridges

The implementation begins by constructing the adjacency list representation of the graph. Since the graph is undirected, each edge is inserted in both directions.

The discovery array tracks when each node was first visited during DFS. The low array tracks the earliest reachable discovery time from the node's subtree.

The DFS function performs the core logic.

When entering a node:

  • Assign the current DFS timestamp
  • Initialize both discovery and low
  • Increment the global time counter

For every neighbor:

  • Skip the parent edge

  • If the neighbor is unvisited:

  • Recurse

  • Propagate low-link values upward

  • Check whether the edge is a bridge

  • Otherwise:

  • Update low-link using the already visited ancestor

Finally, the algorithm returns all detected bridge edges.

Go Solution

package main

func criticalConnections(n int, connections [][]int) [][]int {
	graph := make([][]int, n)

	for _, edge := range connections {
		u, v := edge[0], edge[1]
		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	discovery := make([]int, n)
	low := make([]int, n)

	for i := 0; i < n; i++ {
		discovery[i] = -1
	}

	time := 0
	result := [][]int{}

	var dfs func(int, int)

	dfs = func(node int, parent int) {
		discovery[node] = time
		low[node] = time
		time++

		for _, neighbor := range graph[node] {
			if neighbor == parent {
				continue
			}

			if discovery[neighbor] == -1 {
				dfs(neighbor, node)

				if low[neighbor] < low[node] {
					low[node] = low[neighbor]
				}

				if low[neighbor] > discovery[node] {
					result = append(result, []int{node, neighbor})
				}
			} else {
				if discovery[neighbor] < low[node] {
					low[node] = discovery[neighbor]
				}
			}
		}
	}

	dfs(0, -1)

	return result
}

The Go implementation follows the same algorithmic structure as the Python version.

A few Go-specific details are worth noting:

  • Slices are used for adjacency lists and result storage.
  • Arrays are initialized with zero values, so we explicitly fill discovery with -1 to represent unvisited nodes.
  • Go does not support nested named functions directly, so we define dfs as a function variable before assigning the recursive implementation.
  • Integer overflow is not a concern because timestamps never exceed 10^5.

Worked Examples

Example 1

Input

n = 4
connections = [[0,1],[1,2],[2,0],[1,3]]

Graph

0 --- 1 --- 3
 \   /
   2

DFS Traversal

Step Node discovery low Action
1 0 0 0 Start DFS
2 1 1 1 Visit from 0
3 2 2 2 Visit from 1
4 2 2 0 Back edge to 0
5 1 1 0 Update from child 2
6 3 3 3 Visit from 1
7 1 1 0 Check low[3] > disc[1]

At the final step:

low[3] = 3
discovery[1] = 1

Since:

3 > 1

edge [1,3] is a bridge.

Output

[[1,3]]

Example 2

Input

n = 2
connections = [[0,1]]

Graph

0 --- 1

DFS Traversal

Step Node discovery low Action
1 0 0 0 Start DFS
2 1 1 1 Visit child
3 0 0 0 Check bridge

Since:

low[1] = 1
discovery[0] = 0

and:

1 > 0

edge [0,1] is critical.

Output

[[0,1]]

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Every node and edge is processed once
Space O(n + m) Adjacency list, recursion stack, discovery arrays

The DFS traversal visits each node exactly once. Each undirected edge is examined twice, once from each endpoint. Therefore the total runtime is linear in the size of the graph.

The adjacency list requires O(n + m) space. The discovery and low arrays require O(n), and the recursion stack can reach O(n) depth in the worst case.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = defaultdict(list)

        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)

        discovery = [-1] * n
        low = [-1] * n
        time = 0
        bridges = []

        def dfs(node: int, parent: int):
            nonlocal time

            discovery[node] = time
            low[node] = time
            time += 1

            for neighbor in graph[node]:
                if neighbor == parent:
                    continue

                if discovery[neighbor] == -1:
                    dfs(neighbor, node)

                    low[node] = min(low[node], low[neighbor])

                    if low[neighbor] > discovery[node]:
                        bridges.append(sorted([node, neighbor]))
                else:
                    low[node] = min(low[node], discovery[neighbor])

        dfs(0, -1)

        return bridges

solution = Solution()

# Example 1, single bridge connected to a cycle
assert sorted(solution.criticalConnections(
    4,
    [[0,1],[1,2],[2,0],[1,3]]
)) == [[1,3]]

# Example 2, only one edge
assert sorted(solution.criticalConnections(
    2,
    [[0,1]]
)) == [[0,1]]

# Tree graph, every edge is critical
assert sorted(solution.criticalConnections(
    5,
    [[0,1],[1,2],[2,3],[3,4]]
)) == [[0,1],[1,2],[2,3],[3,4]]

# Complete cycle, no critical edges
assert sorted(solution.criticalConnections(
    4,
    [[0,1],[1,2],[2,3],[3,0]]
)) == []

# Multiple bridges between cyclic components
assert sorted(solution.criticalConnections(
    6,
    [[0,1],[1,2],[2,0],[1,3],[3,4],[4,5],[5,3]]
)) == [[1,3]]

# Dense graph with no bridges
assert sorted(solution.criticalConnections(
    5,
    [[0,1],[0,2],[0,3],[1,2],[1,3],[2,3],[3,4],[2,4],[1,4]]
)) == []

# Minimal valid input
assert sorted(solution.criticalConnections(
    2,
    [[0,1]]
)) == [[0,1]]

# Star graph, all edges critical
assert sorted(solution.criticalConnections(
    5,
    [[0,1],[0,2],[0,3],[0,4]]
)) == [[0,1],[0,2],[0,3],[0,4]]

Test Summary

Test Why
Single bridge attached to cycle Verifies proper bridge detection
Single edge graph Smallest valid graph
Tree graph Every edge should be critical
Pure cycle No edge should be critical
Cyclic components joined by bridge Tests bridge between dense regions
Dense graph Ensures no false positives
Minimal valid input Boundary constraint validation
Star graph Multiple independent bridges

Edge Cases

Tree Structures

A tree contains no cycles, meaning every edge is the only path connecting two regions of the graph.

This is a common source of bugs because the algorithm must correctly identify every edge as a bridge. The implementation handles this naturally because no subtree can reach an ancestor through a back edge, causing every edge to satisfy:

low[child] > discovery[parent]

Fully Cyclic Graphs

In a graph where every node belongs to a cycle, no edge should be critical.

A naive implementation may incorrectly classify edges if it mishandles back edges or parent skipping logic. The algorithm correctly updates low values whenever it encounters an already visited ancestor, preserving the existence of alternate routes.

Long Linear Chains

A graph shaped like a linked list creates the deepest possible DFS recursion depth.

This is important because recursion depth can become large for n = 10^5. Algorithmically the solution remains correct, but in Python this could risk recursion depth limits in some environments. LeetCode's environment generally accommodates recursive DFS for this problem, but iterative DFS or recursion limit adjustment could be considered in production systems.