• <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]
            欧美va久久久噜噜噜久久| 久久99国产综合精品女同| 久久精品亚洲欧美日韩久久 | 香蕉久久影院| 狠狠色狠狠色综合久久| 久久久久四虎国产精品| 一本大道久久香蕉成人网| 精品免费久久久久久久| 天天综合久久一二三区| 99久久99久久精品免费看蜜桃| 精品久久久无码中文字幕天天| 久久精品国产亚洲AV忘忧草18| 久久久久久狠狠丁香| 久久精品免费一区二区| 久久精品国产99国产精品| 天天躁日日躁狠狠久久| 亚洲国产成人精品女人久久久| 久久婷婷五月综合97色一本一本 | 国产99精品久久| 久久久久亚洲AV无码专区首JN | 无码人妻少妇久久中文字幕| 精品999久久久久久中文字幕| 亚洲国产精品嫩草影院久久| 国产2021久久精品| 久久国产精品成人影院| 久久久婷婷五月亚洲97号色| 久久九九久精品国产免费直播| 欧美伊人久久大香线蕉综合69| 99国内精品久久久久久久| 久久成人国产精品二三区| 久久精品国产亚洲AV无码麻豆 | 精品一二三区久久aaa片| 亚洲精品99久久久久中文字幕| 观看 国产综合久久久久鬼色 欧美 亚洲 一区二区 | av国内精品久久久久影院| 久久久精品人妻无码专区不卡| 7国产欧美日韩综合天堂中文久久久久 | 亚洲精品美女久久久久99小说| 久久国产成人午夜aⅴ影院| 久久免费大片| 亚洲日本va午夜中文字幕久久|