• <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]
            97久久香蕉国产线看观看| 久久国产免费观看精品| 国产视频久久| 久久综合久久综合九色| 久久精品国产亚洲沈樵| 国产农村妇女毛片精品久久| 久久久人妻精品无码一区| 国产综合成人久久大片91| 久久综合久久综合九色| 国产精品免费看久久久香蕉| 午夜精品久久久久久影视777| 理论片午午伦夜理片久久| 无码八A片人妻少妇久久| 亚洲国产精品久久久天堂| 国产欧美一区二区久久| 国产成人久久精品麻豆一区| 亚洲伊人久久成综合人影院| 久久国产色AV免费观看| 久久亚洲精品无码播放| 久久久久久久人妻无码中文字幕爆| 久久夜色tv网站| 国产精品久久久久久久久软件| 精品久久久久久成人AV| 午夜精品久久久内射近拍高清| 久久久亚洲欧洲日产国码二区| 国产—久久香蕉国产线看观看| 亚洲色大成网站WWW久久九九| 国产午夜精品久久久久九九电影| 狠狠色丁香婷婷久久综合| 久久91综合国产91久久精品 | 综合久久一区二区三区| 久久久一本精品99久久精品88| 婷婷久久综合九色综合绿巨人| 91精品国产91久久久久久| 久久午夜无码鲁丝片| 91麻豆国产精品91久久久| 韩国三级中文字幕hd久久精品 | 久久国产亚洲精品| 国产精品久久久久久| 老男人久久青草av高清| 伊人久久大香线蕉综合5g|