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