找出無向圖最小生成樹的關(guān)鍵邊和偽關(guān)鍵邊
定義：
An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.
并查集求MST+枚舉邊，思路參考->https://leetcode.com/problems/find-critical-and-pseudo-critical-edges-in-minimum-spanning-tree/solutions/3929349/detailed-video-solution-java-c-python/
1 #1489
2 #Runtime: 2134 ms (Beats 50%)
3 #Memory: 13.4 MB (Beats 100%)
4
5 class UnionFind:
6 def __init__(self, n):
7 self.pa = list(range(n))
8
9
10 def find(self, x):
11 if self.pa[x] != x:
12 self.pa[x] = self.find(self.pa[x])
13 return self.pa[x]
14
15
16 def union(self, x, y):
17 px, py = self.find(x), self.find(y)
18 self.pa[px] = py
19
20
21 class Solution(object):
22 def findCriticalAndPseudoCriticalEdges(self, n, edges):
23 """
24 :type n: int
25 :type edges: List[List[int]]
26 :rtype: List[List[int]]
27 """
28 def find_MST(block, e):
29 uf = UnionFind(n)
30 wt = 0
31 if e != -1:
32 wt += edges[e][2]
33 uf.union(edges[e][0], edges[e][1])
34 for i in range(len(edges)):
35 if i == block:
36 continue
37 if uf.find(edges[i][0]) == uf.find(edges[i][1]):
38 continue
39 uf.union(edges[i][0], edges[i][1])
40 wt += edges[i][2]
41 for i in range(n):
42 if uf.find(i) != uf.find(0):
43 return float('inf')
44 return wt
45
46 c = []
47 pc = []
48 for i, e in enumerate(edges):
49 e.append(i)
50 edges.sort(key=lambda x: x[2])
51 mst = find_MST(-1, -1)
52 for i, e in enumerate(edges):
53 if mst < find_MST(i, -1):
54 c.append(e[3])
55 elif mst == find_MST(-1, i):
56 pc.append(e[3])
57 return [c, pc]