Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
找出无向图最小生成树的关键边和伪关键边

定义:
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]

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理