1192. Critical Connections in a Network
LLancelot opened this issue · 1 comments
LLancelot commented
There are n
servers numbered from 0
to n-1
connected by undirected server-to-server connections
forming a network where connections[i] = [a, b]
represents a connection between servers a
and b
. Any server can reach any other server directly or indirectly through the network.
A critical connection is a connection that, if removed, will make some server 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.
LLancelot commented
代码
class Solution(object):
def criticalConnections(self, n, connections):
"""
:type n: int
:type connections: List[List[int]]
:rtype: List[List[int]]
"""
g = collections.defaultdict(set)
for u, v in connections:
g[u].add(v)
g[v].add(u)
jump = [-1] * n
def dfs(v, parent, level, jump, res, g):
jump[v] = level + 1
for child in g[v]:
if child == parent:
continue
elif jump[child] == -1:
# unvisited node, do dfs
jump[v] = min(jump[v], dfs(child, v, level + 1, jump, res, g))
else:
jump[v] = min(jump[v], jump[child])
if jump[v] == level + 1 and v != 0:
# this is a critical connection
res.append([parent, v])
return jump[v]
# main
res = []
dfs(0, -1, 0, jump, res, g)
return res