题目
树可以看成是一个连通且无环的无向图。给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的边。
例：
输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]
方法：并查集
- n 记录边的数量，因为此时是一个树加一条边导致形成了一个有环的无向图，所以同时也是点的数量
- parent 记录每个节点所在集合的代表节点，初始设置各个节点自己为一个集合，那么每个节点的代表节点为其自己
- 遍历边集合，node1 表示边左边的点，node2 表示边右边的点
- 若两个点的集合的代表节点不同，那么表示两个点不在同一集合，两个点并不相连，将两个点所在集合合并为同一集合，此时两个点可以相连
- 若两个点的集合的代表节点相同，那么表示两个点在同一集合，两个点可以通过某种路径相连，将此时的边加入的话，就会生成环，所以该边即为导致有环的原因，返回该边
find 函数：寻找节点所在集合的代表节点
- 若此节点所在集合的代表节点不为其自身，则需通过调用 find 函数继续寻找其代表节点
- 最终返回该节点的代表节点
union 函数：将两个节点的集合合并，两个集合拥有同一代表节点
- 将第二个节点的代表节点设置为第一个节点的代表节点
class Solution(object):
def findRedundantConnection(self, edges):
n = len(edges)
parent = [i for i in range(n+1)]
def find(index):
if parent[index] != index:
parent[index] = find(parent[index])
return parent[index]
def union(index1, index2):
parent[find(index1)] = find(index2)
for node1, node2 in edges:
if find(node1) != find(node2):
union(node1, node2)
else:
return [node1, node2]
return []
相关知识
-
并查集：
集合树： 所有节点以代表节点为父节点构成的多叉树
节点的代表节点： 可以理解为节点的父节点，从当前节点出发，可以向上找到的第一个节点
集合的代表节点： 可以理解为根节点，意味着该集合内所有节点向上走，最终都能到达的节点
参考
代码相关：https://leetcode.cn/problems/redundant-connection/solution/rong-yu-lian-jie-by-leetcode-solution-pks2/
并查集：https://leetcode.cn/problems/redundant-connection/solution/tong-su-jiang-jie-bing-cha-ji-bang-zhu-xiao-bai-ku/
网友评论