• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            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]
            性做久久久久久久| 亚洲中文字幕无码久久2017| 狠狠色丁香婷婷综合久久来| 91精品国产综合久久婷婷| 国产精品一久久香蕉国产线看 | 国产精品永久久久久久久久久| 久久精品国产福利国产秒| 久久青青草原亚洲av无码| 色偷偷88欧美精品久久久| 久久人人妻人人爽人人爽| 国产成人久久精品区一区二区| 大蕉久久伊人中文字幕| 伊人久久大香线蕉综合热线| 一本色道久久HEZYO无码| 香蕉久久夜色精品国产小说| 热久久最新网站获取| a级成人毛片久久| 久久精品国产免费观看| 国产亚洲成人久久| 久久国产高潮流白浆免费观看| 久久综合一区二区无码| 久久噜噜电影你懂的| 香蕉久久夜色精品升级完成| 久久精品中文字幕第23页| 久久天天躁狠狠躁夜夜96流白浆 | 草草久久久无码国产专区| 伊人久久精品无码二区麻豆| 久久久久这里只有精品 | 97r久久精品国产99国产精| 久久精品国产亚洲AV久| 日本久久久久久久久久| 九九久久精品无码专区| 日本三级久久网| 大伊人青草狠狠久久| 91精品国产色综合久久| 久久久噜噜噜久久熟女AA片 | 99久久国产亚洲高清观看2024 | 国产亚洲色婷婷久久99精品| 亚洲国产精品无码久久一区二区| 久久天天躁夜夜躁狠狠躁2022 | 人妻精品久久久久中文字幕69|