• 注册
  • 捐助

    请在小工具里添加二维码

    • 今日签到
    • 连续签到
  • Tom
    Tom
    今天 00:58
  • Tom
    Tom
    • 查看作者
    • 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:

      Leetcode: 1192. Critical Connections in a Network

      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][0] != connections[i][1]

      • 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 = [10001] * 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[0][0]
              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
    • 884
    • 请登录之后再进行评论

      登录
    • 做任务
    • 实时动态
    • 返回顶部