LeetCode 冗余连接题解

LeetCode 冗余连接题解题目描述给定一个包含 n 个节点的树增加一条边使其变成一个图。返回可以构成环的边。示例输入edges [[1,2], [1,3], [2,3]]输出[2,3]解题思路方法并查集思路使用并查集来解决这个问题。遍历所有边如果两个节点已经在同一个集合中则这条边是冗余的。否则将两个节点合并到同一个集合中。复杂度分析时间复杂度O(n)。空间复杂度O(n)。代码实现class UnionFind: def __init__(self, n): self.parent list(range(n)) def find(self, x): if self.parent[x] ! x: self.parent[x] self.find(self.parent[x]) return self.parent[x] def union(self, x, y): px, py self.find(x), self.find(y) if px py: return False self.parent[px] py return True def find_redundant_connection(edges): n len(edges) uf UnionFind(n 1) for edge in edges: if not uf.union(edge[0], edge[1]): return edge return [] # 测试 def test_find_redundant_connection(): edges [[1, 2], [1, 3], [2, 3]] print(find_redundant_connection(edges)) # 输出[2, 3] if __name__ __main__: test_find_redundant_connection()总结冗余连接是并查集的典型应用找出构成环的边。