一、题目内容

给你一个 n 个点的带权无向连通图，节点编号为 0 到 n-1 ，同时还有一个数组 edges ，其中 edges[i] = [fromi, toi, weighti] 表示在 fromi 和 toi 节点之间有一条带权无向边。最小生成树 (MST) 是给定图中边的一个子集，它连接了所有节点且没有环，而且这些边的权值和最小。

请你找到给定图中最小生成树的所有关键边和伪关键边。如果从图中删去某条边，会导致最小生成树的权值和增加，那么我们就说它是一条关键边。伪关键边则是可能会出现在某些最小生成树中但不会出现在所有最小生成树中的边。

请注意，你可以分别以任意顺序返回关键边的下标和伪关键边的下标。

示例 1：

输入：n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
输出：[[0,1],[2,3,4,5]]
解释：上图描述了给定图。
下图是所有的最小生成树。

注意到第 0 条边和第 1 条边出现在了所有最小生成树中，所以它们是关键边，我们将这两个下标作为输出的第一个列表。
边 2，3，4 和 5 是所有 MST 的剩余边，所以它们是伪关键边。我们将它们作为输出的第二个列表。

示例 2 ：

输入：n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
输出：[[],[0,1,2,3]]
解释：可以观察到 4 条边都有相同的权值，任选它们中的 3 条可以形成一棵 MST 。所以 4 条边都是伪关键边。

提示：

2 <= n <= 100
1 <= edges.length <= min(200, n * (n - 1) / 2)
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti <= 1000
所有 (fromi, toi) 数对都是互不相同的。

二、解题思路

难到爆炸！！并查集， DFS，最小生成树算法，注意遍历边时权重要排序，具体的算法流程看代码注释。

三、代码


  
   
    
     
    
    
     
      from collections import defaultdict
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
     
      class Solution:
     
    
   
    
     
    
    
     
       flag = True
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
      def findCriticalAndPseudoCriticalEdges(self, n: int, edges: list) -> list:
     
    
   
    
     
    
    
     
       f = list(range(n))
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
      def find(x):
     
    
   
    
     
    
    
      if x != f[x]:
     
    
   
    
     
    
    
     
       f[x] = find(f[x])
     
    
   
    
     
    
    
      return f[x]
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
      # weight存储 权重和边下标
     
    
   
    
     
    
    
     
       weight = []
     
    
   
    
     
    
    
      for index, item in enumerate(edges):
     
    
   
    
     
    
    
     
       u, v, w = item
     
    
   
    
     
    
    
     
       weight.append((w, index))
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
      # 构建u到v和v到u的关系（u是起始点，v是终止点）
     
    
   
    
     
    
    
     
       keyedges = defaultdict(list)
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
      # 关键边集合
     
    
   
    
     
    
    
     
       keyedge = set()
     
    
   
    
     
    
    
      # 非关键边集合
     
    
   
    
     
    
    
     
       non_keyedge = set()
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
      def dfs(u, v, fw, visited):
     
    
   
    
     
    
    
      # 起始点和终结点一样，返回True
     
    
   
    
     
    
    
      if u == v:
     
    
   
    
     
    
    
      return True
     
    
   
    
     
    
    
      # 遍历集合加入起始点u
     
    
   
    
     
    
    
     
       visited.add(u)
     
    
   
    
     
    
    
      # 查看u节点的前一个节点tmp和后一个节点tmp
     
    
   
    
     
    
    
      for tmp, index in keyedges[u]:
     
    
   
    
     
    
    
     
       w = edges[index][2]  # 与前一个节点或后一个节点构成的边的权值
     
    
   
    
     
    
    
      if tmp not in visited and dfs(tmp, v, fw, visited):
     
    
   
    
     
    
    
      if w == fw:  # 当前边的权重和上一次得到权重一样，说明两条边都可以分别删除掉
     
    
   
    
     
    
    
     
       keyedge.discard(index)  # 不是关键边，从关键边集合中去除
     
    
   
    
     
    
    
     
       non_keyedge.add(index)  # 非关键边加入
     
    
   
    
     
    
    
     
       self.flag = True
     
    
   
    
     
    
    
      return True
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
      for w, index in sorted(weight):
     
    
   
    
     
    
    
     
       u, v, _ = edges[index]
     
    
   
    
     
    
    
     
       fu = find(u)
     
    
   
    
     
    
    
     
       fv = find(v)
     
    
   
    
     
    
    
      if fu != fv:
     
    
   
    
     
    
    
     
       f[fu] = find(fv)  # 将当前fu节点的终止点变得和fv查找的节点一致
     
    
   
    
     
    
    
     
       keyedges[u].append((v, index))
     
    
   
    
     
    
    
     
       keyedges[v].append((u, index))
     
    
   
    
     
    
    
     
       keyedge.add(index)
     
    
   
    
     
    
    
      else:  # 终止节点一致， 例如[2, 3, 2], [0, 3, 2]， 3和3都是查到的节点
     
    
   
    
     
    
    
     
       visited = set()
     
    
   
    
     
    
    
     
       self.flag = False
     
    
   
    
     
    
    
     
       dfs(u, v, w, visited)
     
    
   
    
     
    
    
      if self.flag:
     
    
   
    
     
    
    
     
       non_keyedge.add(index)
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
      return [list(keyedge), list(non_keyedge)]
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
      
     
    
   
    
     
    
    
     
      if __name__ == '__main__':
     
    
   
    
     
    
    
     
       s = Solution()
     
    
   
    
     
    
    
     
       n = 5
     
    
   
    
     
    
    
     
       edges = [[0, 1, 1], [1, 2, 1], [2, 3, 2], [0, 3, 2], [0, 4, 3], [3, 4, 3], [1, 4, 6]]
     
    
   
    
     
    
    
     
       ans = s.findCriticalAndPseudoCriticalEdges(n, edges)
     
    
   
    
     
    
    
     
       print(ans)

文章来源: nickhuang1996.blog.csdn.net，作者：悲恋花丶无心之人，版权归原作者所有，如需转载，请联系作者。

原文链接：nickhuang1996.blog.csdn.net/article/details/112919119

（完）