資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究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作為引數。
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且d <= 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
更新於: 2020年12月15日
250次瀏覽
廣告