• <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]
            久久精品国产秦先生| 久久人人爽人人爽人人片AV不 | 精品国产乱码久久久久久浪潮 | 久久丫忘忧草产品| 欧美熟妇另类久久久久久不卡| 欧美亚洲色综久久精品国产| 久久91亚洲人成电影网站| 国产精品综合久久第一页| 久久人人爽人人爽人人片AV高清 | 色综合久久综合中文综合网| 国产午夜免费高清久久影院| 久久中文字幕视频、最近更新 | 午夜天堂精品久久久久| 99久久99久久精品国产| 中文精品久久久久人妻不卡| 国产福利电影一区二区三区久久久久成人精品综合 | 国内精品欧美久久精品| 久久久久亚洲AV成人网人人网站| 久久免费精品视频| 人妻精品久久无码区| 欧美国产精品久久高清| 日本免费一区二区久久人人澡 | 久久久久亚洲AV无码麻豆| 久久久无码精品亚洲日韩软件| 亚洲色欲久久久综合网东京热| 久久久久无码专区亚洲av| 久久久久久综合一区中文字幕| 中文字幕久久波多野结衣av| 久久久久久久免费视频| 欧美性猛交xxxx免费看久久久| 国产午夜精品理论片久久影视 | 久久精品国产福利国产琪琪| av无码久久久久久不卡网站 | 久久青青国产| 久久九九久精品国产免费直播| 国产AV影片久久久久久 | 精品久久久久久无码中文字幕一区 | 亚洲国产精品久久久久婷婷老年 | 国产香蕉久久精品综合网| 久久天天婷婷五月俺也去| 99久久这里只精品国产免费|