Abstract / Summary

Find all network connections whose removal increases the number of disconnected parts in the network.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (500k+ submissions).

Typical patterns to solve this problem:

• Biconnected Component
• Depth First Search
• Graph Theory

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation solves the problem of finding all critical connections (bridges) in an undirected graph with n nodes. It follows Tarjan’s algorithm, a depth-first search that records discovery times and low-link values to identify edges whose removal would increase the number of connected components. The solution builds an adjacency list, performs a recursive DFS starting from node 0, and yields each bridge as it is discovered.

Building the adjacency structure

The first logical block transforms the list of edge pairs into a convenient adjacency representation. A defaultdict of lists is used so that each node automatically receives an empty list when first accessed.

next = defaultdict(list)
for a, b in connections:
    next[a].append(b)
    next[b].append(a)

This structure enables constant-time lookup of all neighbors for any node and avoids explicit existence checks when populating the graph.

Timestamp and low-link containers

Two dictionaries, age and low, store the discovery timestamp of each node and the smallest timestamp reachable from that node (including back-edges). A single integer now acts as a global clock that increments with each node visit.

age = {}          # discovery time of each node
low = {}          # earliest reachable discovery time
now = 0           # global timestamp

Using dictionaries rather than fixed-size arrays allows the algorithm to work correctly even if node identifiers are not contiguous.

Recursive depth-first search

The core of the algorithm resides in the nested deeper function. It receives the current node and the node from which it arrived (previous). The function first records the node’s discovery time and initializes its low-link value to the same timestamp.

def deeper(node, previous=None):
    nonlocal now, next, age, low

    age[node] = now
    low[node] = now
    now += 1

The recursion then iterates over all neighbors of the current node. The check if neighbor == previous skips the edge that leads back to the parent in the DFS tree, preventing an immediate trivial cycle.

    for neighbor in next[node]:
        if neighbor == previous:
            continue

When a neighbor has not yet been visited (neighbor not in age), the function recurses into that neighbor, yielding any bridges discovered deeper in the call stack.

        if neighbor not in age:
            yield from deeper(neighbor, node)

After returning from the recursive call, the low-link value of the current node is potentially lowered by the low-link of the neighbor, reflecting the ability to reach an earlier node through the neighbor’s subtree.

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

The bridge detection condition follows directly from Tarjan’s theory: if the lowest reachable timestamp from the neighbor’s subtree is greater than the discovery time of the current node, the edge connecting them cannot be part of any cycle and is therefore critical.

        if low[neighbor] > age[node]:
            yield [node, neighbor]

Initiating the search

The outer function starts the DFS from node 0, which is sufficient for a connected graph. The generator deeper yields each bridge as a two-element list, and the outer generator forwards those results to the caller.

yield from deeper(0)

Because the function is a generator, the caller receives a lazy sequence of critical connections without constructing an intermediate list.

Edge-case handling

The algorithm gracefully handles graphs where a node has no outgoing edges: the adjacency list entry will be an empty list, the DFS loop will simply terminate, and no bridges are emitted. Self-loops are ignored by the neighbor == previous guard, as a self-loop would appear as a neighbor equal to the current node’s parent in the recursion tree. Multiple parallel edges are treated as separate entries in the adjacency list; each parallel edge is examined independently, and the low-link logic correctly determines whether any of them constitute a bridge. The use of dictionaries for age and low means that sparse node identifiers (e.g., nodes numbered 0 and 1000 only) do not cause index errors.

Performance optimizations

The choice of defaultdict(list) eliminates the need for explicit existence checks when appending neighbors, reducing overhead in the graph construction phase. Storing timestamps in a single integer now that increments monotonically avoids the cost of generating unique identifiers through more complex mechanisms. The algorithm updates the low-link value in place, avoiding additional data structures or copying. By yielding bridges immediately when they are discovered, the implementation avoids storing all results in memory, which is advantageous for very large graphs where the number of bridges could be substantial. The recursion leverages Python’s generator yield from construct to propagate results without intermediate collections, keeping the call stack lightweight.

Overall, the code presents a concise and faithful implementation of Tarjan’s bridge-finding algorithm, with careful handling of typical graph edge cases and thoughtful use of Python’s built-in data structures to achieve efficient execution.

Imagine a magical forest where every tree is connected to others by secret rope bridges. Some of these bridges are extra special because if they break, you would be trapped and unable to visit certain parts of the forest anymore. This computer program acts like a tiny explorer running across these bridges to find out which ones are the most important.

First, the program draws a map of all the bridges so it knows which trees are connected to each other. It starts at the very first tree and begins walking deeper and deeper into the forest. As it walks, it keeps a backpack filled with little notes. One note remembers the order in which the explorer reached each tree, like tagging them with a time stamp. Another note keeps track of the furthest back the explorer can go to reach an old part of the forest.

When the explorer reaches a tree, it looks at all the paths leading forward. If it sees a bridge that leads to a place it has already visited, it ignores it. If it sees a path leading to a new tree, it travels there and keeps exploring. Once there is nowhere else to go, the explorer checks its notes. If it realizes that a bridge it just crossed leads to a tree that cannot reach back to the beginning of the path through any other way, that bridge is marked as a critical connection. This means that if that specific bridge disappears, that part of the forest becomes stuck. After checking all the paths, the program collects all these important bridges and shows them to you.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Python		Java				TS
	WalkCCC	C++			Java
	leetcode.ca	C++	Python		Java			Go	TS
	Progiez	C++	Python		Java
github	BigEggStudy					C#
	black-shadows	C++
	charles-wangkai				Java
	everthis			JS
	fpdjsns	C++
	fsq	C++
	JoshCrozier			JS
	keineahnung2345	C++
	lkwq007		Python
	martianoff						Scala
	suxrobGM					C#
	trung-hn		Python
	varunu28				Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fpdjsns	C++
fsq	C++
JoshCrozier	JavaScript
keineahnung2345	C++
lkwq007	Python
martianoff	Scala
suxrobGM	C#
trung-hn	Python
varunu28	Java
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality