https://leetcode.com/problems/critical-connections-in-a-network/
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.
- code
class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
rank = defaultdict(int)
graph = defaultdict(list)
conn_dict = {}
for i, j in connections:
graph[i].append(j)
graph[j].append(i)
if i > j: i, j = j, i
conn_dict[(i, j)] = 1
def dfs(node, cur_rank):
if rank[node] != 0:
return rank[node]
rank[node] = cur_rank
min_rank = cur_rank + 1
for nex in graph[node]:
if rank[nex] != 0 and rank[nex] == cur_rank - 1:
continue
recur_rank = dfs(nex, cur_rank + 1)
if recur_rank <= cur_rank:
del conn_dict[min(node, nex), max(node, nex)]
min_rank = min(min_rank, recur_rank)
return min_rank
dfs(0, 0)
res = []
for i, j in conn_dict:
res.append([i, j])
return res