Critical Connections in a Network — LeetCode 1192 Python Solution

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 ans

Complexity

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