1192. Critical Connections in a Network
On LeetCode ->Problem¶
Given a connected undirected graph of n servers, return every edge whose removal disconnects the graph.
Key trick¶
Use Tarjan's bridge-finding algorithm with discovery times and low-link values. A DFS tree edge (u, v) is critical exactly when low[v] > discovery[u], meaning v cannot reach u or an ancestor of u without that edge.
Trap¶
- Detecting whether vertices belong to cycles is insufficient because bridges are properties of edges.
- DFS must skip the parent edge and handle already visited neighbors without recursing again.
- A recursive implementation must account for graphs with depth up to \(10^5\).
Why is it interesting?¶
It finds every bridge in one traversal by determining how far each DFS subtree can reconnect toward the root.
Python solution¶
import sys
class Solution:
def criticalConnections(self, n: int, connections: list[list[int]],) -> list[list[int]]:
sys.setrecursionlimit(max(sys.getrecursionlimit(), 2 * n + 10))
graph = [[] for _ in range(n)]
for a, b in connections:
graph[a].append(b)
graph[b].append(a)
discovery = [-1] * n
low = [0] * n
time = 0
res = []
def dfs(node: int, parent: int) -> None:
nonlocal time
discovery[node] = low[node] = time
time += 1
for nei in graph[node]:
if nei == parent:
continue
if discovery[nei] == -1:
dfs(nei, node)
low[node] = min(low[node], low[nei])
# The neighbor's subtree cannot reconnect to node or above.
if low[nei] > discovery[node]:
res.append([node, nei])
else:
# A back edge reconnects to an already discovered vertex.
low[node] = min(low[node], discovery[nei])
dfs(0, -1)
return res
# Iterative DFS
def criticalConnections_2(self, n: int, connections: list[list[int]],) -> list[list[int]]:
graph = [[] for _ in range(n)]
for a, b in connections:
graph[a].append(b)
graph[b].append(a)
discovery = [-1] * n
low = [0] * n
parent = [-1] * n
res = []
discovery[0] = low[0] = 0
time = 1
# Each frame contains the vertex and its next neighbor index.
stack = [[0, 0]]
while stack:
node, i = stack[-1]
if i < len(graph[node]):
nei = graph[node][i]
stack[-1][1] += 1
if nei == parent[node]:
continue
if discovery[nei] == -1:
parent[nei] = node
discovery[nei] = low[nei] = time
time += 1
stack.append([nei, 0])
else:
# A non-parent edge may reconnect to an ancestor.
low[node] = min(low[node], discovery[nei])
else:
# All descendants have been processed, so low[node] is final.
stack.pop()
p = parent[node]
if p != -1:
if low[node] > discovery[p]:
res.append([p, node])
low[p] = min(low[p], low[node])
return res
Time complexity: \(O(n + e)\), where \(e\) is the number of connections.
Space complexity: \(O(n + e)\), including the graph and DFS stack.
Comment on my solution¶
detect_cyclehas no visited set and does not exclude the parent, so it repeatedly traverses undirected edges and can recurse forever.- Marking vertices as
in_cycleloses the required edge-level information. - A bridge may connect two vertices that each belong to different cycles, so checking whether both endpoints are in cycles is incorrect.
- Starting a new cycle search for many edges also makes the approach potentially exponential rather than \(O(n + e)\).
# WRONG
# Time Limit Exceeded: 0/19 testcases passed
# 4, [[0,1],[1,2],[2,0],[1,3]]
# I think it's because the cycle detection with backtracking
# can enter in a cycle excluding start and so recurse for ever
class Solution:
def criticalConnections(self, n: int, connections: list[list[int]]) -> list[list[int]]:
graph = [[] for _ in range(n)]
for a, b in connections:
graph[a].append(b)
graph[b].append(a)
path = []
in_cycle = [False] * n
def detect_cycle(start, cur):
# path is a cycle
if cur == start:
for node in path:
in_cycle[node] = True
return
for nei in graph[cur]:
if not in_cycle[nei]:
path.append(nei)
detect_cycle(start, nei)
path.pop()
for a, b in connections:
if not in_cycle[a] and not in_cycle[b]:
detect_cycle(a, b)
res = []
for a, b in connections:
if not in_cycle[a] and not in_cycle[b]:
res.append([a,b])
return res
Extra¶
Tarjan's bridge-finding algorithm¶
Ok I couldn't find the solution, I don't know about Tarjan's DFS with discovery times and low-link values.
Explain me Tarjan's DFS with discovery times and low-link values.
Core idea¶
A normal DFS tells us the parent-child structure of the traversal. Tarjan's bridge algorithm adds two values for every vertex:
disc[u]: when DFS first visitsu.low[u]: the earliest discovered vertex reachable fromu's DFS subtree without using the edge fromuto its parent.
low[u] summarizes whether the subtree rooted at u has another route back toward an ancestor.
Discovery times¶
Assign an increasing number when entering each vertex.
For this graph:
A possible DFS order is:
The DFS tree might be:
The edge 2 -> 0 reconnects the subtree to an ancestor. It is called a back edge.
Low-link values¶
Initially, a vertex can reach itself:
While examining an edge from u to v, there are two cases.
v is unvisited¶
The edge is a DFS tree edge. Visit v, then propagate what its subtree can reach:
v was already visited¶
If v is not the parent, the edge provides another route to an earlier vertex:
We use disc[v], not low[v], because this edge directly reaches v; using low[v] could incorrectly borrow paths outside the current DFS subtree.
Detecting a bridge¶
After returning from child v to parent u, examine:
If true, (u, v) is a bridge.
This means the subtree rooted at v cannot reach u or any ancestor of u through another edge. Therefore, removing (u, v) disconnects that subtree.
If instead:
then v's subtree has another route to u or one of its ancestors, so (u, v) belongs to a cycle and is not a bridge.
Example trace¶
For the triangle 0-1-2-0 with the tail 1-3:
Vertex 2 sees the already visited vertex 0:
Returning from 2 to 1:
Therefore, (1, 2) is not a bridge.
Its low value propagates upward:
Vertex 3 has no alternative route:
Returning from 3 to 1:
Therefore, (1, 3) is a bridge.
Complete DFS logic¶
def dfs(u, parent):
nonlocal time
disc[u] = low[u] = time
time += 1
for v in graph[u]:
if v == parent:
continue
if disc[v] == -1:
dfs(v, u)
# Anything v's subtree can reach is also reachable from u.
low[u] = min(low[u], low[v])
# v's subtree has no alternative route to u or above.
if low[v] > disc[u]:
bridges.append([u, v])
else:
# A back edge reaches an already discovered vertex.
low[u] = min(low[u], disc[v])
What your cycle approach was missing¶
You were trying to explicitly find and mark cycles. Low-link values avoid that by storing only the most useful fact:
What is the earliest vertex this entire subtree can reach through another route?
Also, being part of a cycle is a property of an edge, not just a vertex. Two vertices can each belong to separate cycles while the edge connecting those cycles is still a bridge.
The algorithm visits each vertex and edge only a constant number of times:
- Time: \(O(V + E)\)
- Space: \(O(V + E)\), including the graph and recursion stack.
Complement on Tarjan's algo¶
- The relation parent-child and ancestors only makes sens during the DFS traversal. Right? This is not a property of the graph by itself in general as it would be in a tree? Am I missing something?
- Is
discoveryandlowglobal or per subtrees?- It's clear that
discorverystores temporal values. Is it also the case forlow? It's not that clear for me. "low[u]: the earliest discovered vertex reachable fromu's DFS subtree without using the edge fromuto its parent."- I intuit what is a bridge but can you define it for me in that context.
- Explain me this comment "The problem guarantees connectivity; the loop also handles forests." above the last for loop.
Parent, child, and ancestor¶
Yes. These relationships belong to the DFS traversal tree, not to the original graph.
An undirected graph does not generally have parents or ancestors. DFS imposes a temporary tree structure based on:
- The starting vertex.
- The order in which neighbors are visited.
For example, the same triangle can produce different DFS trees:
One DFS might produce:
Another might produce:
The parent-child relationships differ, but Tarjan's algorithm finds the same bridges regardless of the chosen DFS tree.
Edges used to discover new vertices are tree edges. Other edges connecting a descendant to an already visited ancestor are back edges.
Are discovery and low global or per subtree?¶
They are global arrays with one entry per vertex:
However, low[u] summarizes information about the DFS subtree rooted at u.
So:
- The arrays are global to the complete DFS.
- Each value belongs to one vertex.
- A
lowvalue is calculated using information from that vertex's descendants.
This lets information propagate upward:
Is low temporal?¶
low[u] is a discovery timestamp, but it is not the time when something happened to u.
It is the smallest discovery timestamp that the subtree rooted at u can reach through an appropriate back edge.
A more precise definition is:
Here, a is an ancestor reachable by a back edge from u or one of u's descendants.
Operationally:
Then low[u] may decrease as DFS discovers alternative routes:
For example:
If the subtree rooted at 2 has a back edge to 0, then:
This does not mean vertex 2 was visited at time 0. It means its subtree can reconnect to the vertex that was visited at time 0.
discovery[u] becomes fixed when u is first visited. low[u] starts at that value, may decrease during DFS, and becomes final when dfs(u) returns.
Why not simply say "reachable"?¶
Because every vertex in a connected graph is reachable from every other vertex. That definition would make all low values equal to the root's discovery time.
low[u] considers a restricted structure:
- Move downward through zero or more DFS tree edges inside
u's subtree. - Then use a back edge to reach
uor one of its ancestors. - Do not use the tree edge connecting
uto its parent as the escape route.
It answers:
Does this subtree have another edge leading back to the already visited part above it?
Bridge definition¶
In graph theory, a bridge is an edge whose removal increases the number of connected components.
In a connected graph, removing a bridge makes the graph disconnected.
In the context of DFS, suppose u is the parent of v:
The tree edge (u, v) is a bridge when:
This means the entire subtree rooted at v has no back edge to:
u, which has timestampdiscovery[u].- Any ancestor of
u, which has a smaller timestamp.
Therefore, (u, v) is the subtree's only connection to the rest of the graph.
If:
then the subtree has another route to u or above:
That alternative route forms a cycle, so removing (u, v) does not disconnect the graph.
Connectivity and the last loop¶
The loop was:
# The problem guarantees connectivity; the loop also handles forests.
for node in range(n):
if discovery[node] == -1:
dfs(node, -1)
Because the problem guarantees that the graph is connected, this would be enough:
Starting from 0 would eventually visit every vertex.
The loop makes the implementation also work for a disconnected graph:
After dfs(0, -1), vertices 3 and 4 remain undiscovered. The loop eventually reaches 3 and starts another DFS.
Each DFS creates one tree. Together, the trees form a DFS forest:
Thus, "handles forests" more precisely means that it handles disconnected graphs by producing a DFS forest. If the graph itself is an actual forest, every edge will be identified as a bridge.
Iterative implementation of Tarjan's algo¶
Ok. I get the Tarjan's bridges algo. Let's go back to the implementation.
Why do you have to use
sys.setrecursionlimit()? Wouldn't be better to write an iterative DFS here?
Yes, an iterative DFS is more robust here. The recursive version is usually shown because it expresses Tarjan's postorder logic clearly, but Python's recursion limit makes it unsafe for this constraint.
Why sys.setrecursionlimit() was needed¶
Python's default recursion limit is usually around 1000, while this graph may contain \(10^5\) vertices.
A path-shaped graph produces DFS depth \(n\):
The recursive implementation would raise:
Increasing the limit allows deeper Python calls, but it does not enlarge the underlying C stack. A sufficiently deep recursion can still consume substantial memory or, depending on the environment, crash the process.
LeetCode often accepts this technique, but it is not the most robust production choice.
Why iterative DFS is less obvious¶
Tarjan's algorithm must perform work both:
- When first entering a vertex.
- After finishing a child's entire subtree.
Recursive DFS provides the second event naturally:
With an iterative DFS, the stack must explicitly remember whether a vertex is being entered or exited. Only on exit is the child's low value final.
Iterative implementation¶
class Solution:
def criticalConnections(
self,
n: int,
connections: list[list[int]],
) -> list[list[int]]:
graph = [[] for _ in range(n)]
for a, b in connections:
graph[a].append(b)
graph[b].append(a)
discovery = [-1] * n
low = [0] * n
parent = [-1] * n
time = 0
res = []
for start in range(n):
if discovery[start] != -1:
continue
discovery[start] = low[start] = time
time += 1
# Each frame stores the vertex and its next neighbor index.
stack = [[start, 0]]
while stack:
node, i = stack[-1]
if i < len(graph[node]):
nei = graph[node][i]
stack[-1][1] += 1
if nei == parent[node]:
continue
if discovery[nei] == -1:
parent[nei] = node
discovery[nei] = low[nei] = time
time += 1
stack.append([nei, 0])
else:
# A visited non-parent neighbor gives a back edge.
low[node] = min(low[node], discovery[nei])
else:
# Exiting node: its low value is now final.
stack.pop()
p = parent[node]
if p == -1:
continue
if low[node] > discovery[p]:
res.append([p, node])
low[p] = min(low[p], low[node])
return res
Time complexity: \(O(n + e)\).
Space complexity: \(O(n + e)\).
For an interview, the recursive solution is often preferable initially because it makes the invariant easier to explain. The iterative version is the stronger final implementation when Python stack safety and the \(10^5\) constraint matter.
Iterative implementation for connected graphs¶
Write the iterative version but without the unecessary loop as the graph is garanteed to be connected. There's only on BFS traversal under this LeetCode constraints.
The graph is connected, so one DFS from vertex 0 visits every vertex. BFS is not used because low-link values require postorder processing.
class Solution:
def criticalConnections(
self,
n: int,
connections: list[list[int]],
) -> list[list[int]]:
graph = [[] for _ in range(n)]
for a, b in connections:
graph[a].append(b)
graph[b].append(a)
discovery = [-1] * n
low = [0] * n
parent = [-1] * n
res = []
discovery[0] = low[0] = 0
time = 1
# Each frame contains the vertex and its next neighbor index.
stack = [[0, 0]]
while stack:
node, i = stack[-1]
if i < len(graph[node]):
nei = graph[node][i]
stack[-1][1] += 1
if nei == parent[node]:
continue
if discovery[nei] == -1:
parent[nei] = node
discovery[nei] = low[nei] = time
time += 1
stack.append([nei, 0])
else:
# A non-parent edge may reconnect to an ancestor.
low[node] = min(low[node], discovery[nei])
else:
# All descendants have been processed, so low[node] is final.
stack.pop()
p = parent[node]
if p != -1:
if low[node] > discovery[p]:
res.append([p, node])
low[p] = min(low[p], low[node])
return res
Time complexity: \(O(n + e)\).
Space complexity: \(O(n + e)\).