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