Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

1300. Critical Connections in a Network

My accepted Python solution to LeetCode problem 1300, Critical Connections in a Network, running in 267ms.

  • Difficulty: Hard
  • Python
  • Runtime 267ms
  • Memory 72.5MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 267ms, memory 72.5MB, accepted 2025-12-29.

python
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(200000)
        
        # Build adjacency list
        graph = defaultdict(list)
        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)
        
        # Tarjan's algorithm for finding bridges
        disc = [-1] * n  # Discovery time
        low = [-1] * n   # Lowest reachable discovery time
        bridges = []
        time = [0]
        
        def dfs(node, parent):
            disc[node] = low[node] = time[0]
            time[0] += 1
            
            for neighbor in graph[node]:
                if disc[neighbor] == -1:  # Not visited
                    dfs(neighbor, node)
                    low[node] = min(low[node], low[neighbor])
                    
                    # If low[neighbor] > disc[node], edge is a bridge
                    if low[neighbor] > disc[node]:
                        bridges.append([node, neighbor])
                elif neighbor != parent:
                    low[node] = min(low[node], disc[neighbor])
        
        # Start DFS from node 0
        dfs(0, -1)
        
        return bridges

Source