本文主要是介绍力扣-684 冗余连接,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
# 利用并查集
class Solution:def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:n = len(edges)parent = list(range(n+1))def find(index): # 找到当前节点index的父节点if parent[index]==index:return indexelse:return find(find(parent[index]))def union(index1, index2): # 将两个节点连在同一个根节点上parent[find(index1)] = find(index2)for index1, index2 in edges: # 判断两个节点是不是同一个根节点if find(index1) == find(index2):return [index1, index2]else:union(index1, index2)
参考:
https://leetcode-cn.com/problems/redundant-connection/solution/684-rong-yu-lian-jie-bing-cha-ji-ji-chu-eartc/
https://leetcode-cn.com/problems/redundant-connection/solution/rong-yu-lian-jie-by-leetcode-solution-pks2/
这篇关于力扣-684 冗余连接的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!