#1192

Critical Connections in a Network

expert · 1190 · lc hard +32 · verified · 59.3% accepted · 6,677 likes · top 57%

⚑ Tarjan's SCC / Bridges / Articulation Points

Description

A network has n servers numbered 0 to n - 1, connected by undirected edges listed in connections, where connections[i] = [ai, bi] links server ai to server bi. Every server can reach every other server through the network.

A critical connection is any edge whose removal would disconnect at least one pair of servers.

Return every critical connection in any order.

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]

Output: [[1,3]]

Explanation: [[3,1]] is also accepted.

Example 2:

Input: n = 2, connections = [[0,1]]

Output: [[0,1]]

Code

1

2

3

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]: