在Python中找到使图断开连接的边缘

假设我们有一个无向图，它已经被表示为邻接表，其中 graph[i] 表示节点 i 的相邻节点。我们必须找到满足以下条件的边的数量。

如果移除边，则图将变为不连通。

因此，如果输入是这样的 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, 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