Skip to content

1300. Critical Connections In A Network

Depth-First Search Graph Theory Biconnected Component

Problem - Critical Connections In A Network

Hard

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.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network 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]]

 

Constraints:

  • 2 <= n <= 105
  • n - 1 <= connections.length <= 105
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • There are no repeated connections.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:

        graph = [[] for _ in range(n)]
        for a, b in connections:
            graph[a].append(b)
            graph[b].append(a)

        dfn = [0] * n
        low = [0] * n
        now = 0

        def tarjan(a: int, val: int):
            nonlocal now
            now += 1
            dfn[a] = low[a] = now
            for b in graph[a]:
                if b == val:
                    continue
                if not dfn[b]:
                    tarjan(b, a)
                    low[a] = min(low[a], low[b])
                    if low[b] > dfn[a]:
                        result.append([a, b])
                else:
                    low[a] = min(low[a], dfn[b])

        result = []
        tarjan(0, -1)
        return result

Submission Stats:

  • Runtime: 199 ms (81.19%)
  • Memory: 96.7 MB (73.96%)