• En
  • Signup
  • 刷题上岸
  • Today 0
  • Post 12
  • Followed 1
  • 捐助

    请在小工具里添加二维码

    刷题上岸 刷题上岸 关注:1 内容:12

    Amazon | OA 2019 | Critical Routers

  • 查看作者
  • 打赏作者
  • 拉黑名单
    • 刷题上岸
    • 等级6
      土豪

      You are given an undirected connected graph. An articulation point (or cut vertex) is defined as a vertex which, when removed along with associated edges, makes the graph disconnected (or more precisely, increases the number of connected components in the graph). The task is to find all articulation points in the given graph.

      Input:
      The input to the function/method consists of three arguments:

      • numNodes, an integer representing the number of nodes in the graph.

      • numEdges, an integer representing the number of edges in the graph.

      • edges, the list of pair of integers - A, B representing an edge between the nodes A and B.

      Output:
      Return a list of integers representing the critical nodes.

      Example:

      Input: numNodes = 7, numEdges = 7, edges = [[0, 1], [0, 2], [1, 3], [2, 3], [2, 5], [5, 6], [3, 4]]

      Amazon | OA 2019 | Critical Routers

      Output: [2, 3, 5]

      Related problems:

      import collections
      numRouters = 7
      numLinks = 7
      Links = [[0,1], [0, 2], [1, 3], [2, 3], [2, 5], [5, 6], [3,4]]
      def criticalRouters(nr,nl,connections):
          graph = collections.defaultdict(list)
          for u, v in connections:
              graph[u].append(v)
              graph[v].append(u)
          def iscon(node):
              visit=[]
              queue = []
              queue.append(0)
              visit.append(0)
              while queue:
                  cur = queue.pop(0)
                  for each in graph[cur]:
                      #print(each)
                      if each not in visit and each != node:
                          visit.append(each)
                          queue.append(each)
              return(visit)
          res = []
          for each in range(nr):
              if len(iscon(each)) < nr-1:
                  res.append(each)
          return res
      r = criticalRouters(numRouters,numLinks,Links)
      print (r)

      请登录之后再进行评论

      登录
    • Tasks
    • Current Activities
    • Back to Top