HardNo. 1192
Critical Connections in a Network — LeetCode 1192 Python Solution
- Pattern
- Depth-First Search
- Topics
- Depth-First Search, Graph, Biconnected Component
- Reading time
- 5 min
- Source
- leetcode.com
The problem
There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network.
Example
- Input
- n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
- Output
- [[1,3]]
- Explanation
- [[3,1]] is also accepted.
Python solution
class Solution:
def criticalConnections(
self, n: int, connections: List[List[int]]
) -> List[List[int]]:
def tarjan(a: int, fa: int):
nonlocal now
now += 1
dfn[a] = low[a] = now
for b in g[a]:
if b == fa:
continue
if not dfn[b]:
tarjan(b, a)
low[a] = min(low[a], low[b])
if low[b] > dfn[a]:
ans.append([a, b])
else:
low[a] = min(low[a], dfn[b])
g = [[] for _ in range(n)]
for a, b in connections:
g[a].append(b)
g[b].append(a)
dfn = [0] * n
low = [0] * n
now = 0
ans = []
tarjan(0, -1)
return ansComplexity
- Time
- O(V+E)
- Space · auxiliary
- O(V)
Pattern: Depth-First Search
Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 1192. Critical Connections in a Network is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Depth-First Search and Graph.
The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0207 | Course Schedule | Medium |
| 0210 | Course Schedule II | Medium |
| 0310 | Minimum Height Trees | Medium |
| 0332 | Reconstruct Itinerary | Hard |
| 0399 | Evaluate Division | Medium |
| 0547 | Number of Provinces | Medium |
Frequently asked questions
- How hard is LeetCode 1192. Critical Connections in a Network?
LeetCode 1192. Critical Connections in a Network is rated Hard on LeetCode.
- What is the time complexity of LeetCode 1192. Critical Connections in a Network?
The Python solution on this page runs in O(V+E).
- What is the space complexity of LeetCode 1192. Critical Connections in a Network?
The Python solution on this page uses O(V) auxiliary space.
- What topics does LeetCode 1192. Critical Connections in a Network cover?
LeetCode 1192. Critical Connections in a Network is tagged Depth-First Search, Graph and Biconnected Component on LeetCode.