Python程序查找断开图的边

假设我们得到一个用邻接表表示的无向图，其中graph[i]表示节点i的邻居节点。我们需要找到满足以下条件的边的数量。

如果移除该边，图将变得不连通。

So, if the input is like graph = [
   [0, 2],
   [0, 4],
   [1, 2, 3],
   [0, 3, 4],
   [4],
   [3],
   [2]
],

那么输出将是1。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数dfs()。它将接收curr、pre、d作为参数。

    • ans := 无穷大

    • dep[curr] := d

    • 对于graph[curr]中的每个邻接节点adj，执行以下操作：

      • 如果pre与adj相同，则

        • 继续下一个迭代，不执行其他步骤

      • 如果dep[adj]不等于-1，则

        • ans := ans和dep[adj]的最小值

      • 否则，

        • ans := ans和dfs(adj, curr, d + 1)的最小值

    • 如果d > 0且d <= ans，则

      • re := re + 1

    • 返回ans

  • 现在，从主函数调用函数dfs()。

  • dep := 一个大小为图的大小并初始化为-1的列表。

  • re := 0

  • dfs(0, -1, 0)

  • 返回re

让我们看看下面的实现来更好地理解：

示例

 在线演示

class Solution:
   def solve(self, graph):
      dep = [−1] * len(graph)
      INF = int(1e9)
      self.re = 0
      def dfs(curr, pre, d):
         ans = INF
         dep[curr] = d
         for adj in graph[curr]:
            if pre == adj:
               continue
            if dep[adj] != −1:
               ans = min(ans, dep[adj])
            else:
               ans = min(ans, dfs(adj, curr, d + 1))
         if d > 0 and d <= ans:
            self.re += 1
         return ans
      dfs(0, −1, 0)
      return self.re
ob = Solution()
print(ob.solve(graph = [
   [0, 2],
   [0, 4],
   [1, 2, 3],
   [0, 3, 4],
   [4],
   [3],
   [2]
]))

输入

graph = [
   [0, 2],
   [0, 4],
   [1, 2, 3],
   [0, 3, 4],
   [4],
   [3],
   [2]
]

输出

1

更新于: 2020年12月15日

250次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告