找出在Python中断开图形连接的边的程序

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们已经提供了一个无向图，它被表示为一个邻接表，其中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

    以上是 找出在Python中断开图形连接的边的程序 的全部内容， 来源链接： utcz.com/z/321457.html

    回到顶部