• En
• Signup

请在小工具里添加二维码

• 今日签到
• 连续签到

暂没有数据

暂没有数据

• 查看作者
• # Leetcode: 1192. Critical Connections in a Network

1192. Critical Connections in a Network
Hard

17619FavoriteShare

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.

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.`

Constraints:

• `1 <= n <= 10^5`

• `n-1 <= connections.length <= 10^5`

• `connections[i] != connections[i]`

• There are no repeated connections

```class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
# graph = [[] for i in range(n)]
graph = collections.defaultdict(list)
visit = [-1] * n
low =  * n

for u, v in connections:
graph[u].append(v)
graph[v].append(u)

def dfs(cur, prev, depth):
if visit[cur] != -1:
return low[cur]
low[cur] = visit[cur] = depth
for nex in graph[cur]:
if nex == prev:
continue
low[cur] = min(low[cur], dfs(nex, cur, depth + 1))
return low[cur]

start = connections
dfs(start, -1, 0)

ans = []
for connection in connections:
u, v  = connection
if low[v] > visit[u] or low[u] > visit[v]:
ans.append(connection)
return ans```

纽约州·法拉盛
• 0
• 0
• 0
• 734
• 请登录之后再进行评论