from typing import List
# 這道題本質上還是利用并查集的知識，首先計算最小的權重和，去除掉無效的邊，
# 然后遍歷所有的邊，然后計算最小的權重和，同時判斷是否可以連通，
# 并查集的模板，
class DSU:
def __init__(self,n):
# 實體化一個串列，用來存放所有的節點對應的父節點，
self.father = list(range(n))
def find(self,x):
# 尋找父節點，判斷父節點是否是自己，
if x != self.father[x]:
# 尋找到最上層的父親節點，
self.father[x] = self.find(self.father[x])
# 回傳，
return self.father[x]
def union(self,x,y):
# 聯合，連接節點，
if not self.is_connected(x,y):
# 尋找到最上層的x的父親節點，讓他等于y的父親節點，
self.father[self.find(x)] = self.find(y)
# 判斷兩個節點是否相連，
def is_connected(self,x,y):
return self.find(x) == self.find(y)
class Solution:
def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
# 在原有的串列中添加位置索引，
sorted_edges = [[index] + i for index,i in enumerate(edges)]
# 根據邊的權重對邊進行排序，
sorted_edges = sorted(sorted_edges,key = lambda x : x[-1])
# 計算最小生成樹的權重和，
total = 0
dsu = DSU(n)
for index2,x,y,w in sorted_edges:
if not dsu.is_connected(x,y):
dsu.union(x,y)
total += w
key_edge = [] # 關鍵邊串列
no_key_edge = [] # 偽關鍵邊串列，
for i,edge in enumerate(sorted_edges):
(j,x,y,w) = edge
# 去掉當前邊，形成新的串列，
cur_edges = sorted_edges[:i] + sorted_edges[i+1:]
# 這里我們先把當前邊相連，然后在進行計算權重和，
# 判斷權重和和最小權重和是否相同，
# 如果不相同的話，那么這條邊就是無效的邊，所以就跳出這一次回圈，
total1 = 0
dsu1 = DSU(n)
dsu1.union(x,y)
total1 += w
for index2, cur_x, cur_y, cur_w in cur_edges:
if not dsu1.is_connected(cur_x, cur_y):
dsu1.union(cur_x, cur_y)
total1 += cur_w
# 如果不相等說明是無效邊，
if total1 != total:
continue
# 下邊是判斷是否為關鍵邊，
# 下邊我們不將當前邊對應的兩個節點相連，
# 然后進行計算最小權重和，如果當前邊是關鍵邊的話，
# 那么我們是不能保證能夠讓所有的節點相連的，
# 所以計算的權重和total2 和 total1是不相同的，
total2 = 0
dsu2 = DSU(n)
for index2, cur_x, cur_y, cur_w in cur_edges:
if not dsu2.is_connected(cur_x, cur_y):
dsu2.union(cur_x, cur_y)
total2 += cur_w
# 判斷是否為關鍵邊，
if total1 != total2:
key_edge.append(edge[0])
else:
no_key_edge.append(edge[0])
return [key_edge,no_key_edge]
A = Solution()
print(A.findCriticalAndPseudoCriticalEdges(n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/255469.html
標籤：Python