找出在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

• re：= re + 1

• 如果pre与adj相同，则

• 如果dep [adj]与-1不同，则

• 除此以外，

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

• ans：= ans的最小值，dep [adj]

• ans：= ans，dfs（adj，curr，d + 1）的最小值

• ans：=无限

• dep [curr]：= d

• 对于graph [curr]中的每个adj，执行

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

• 返回ans

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

• dep：=用-1初始化的图形大小的列表。

• 回复：= 0

• dfs(0,-1,0)

• 返回再

让我们看下面的实现以更好地理解-

示例

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