树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的那个。
示例 1:
输入: edges = [[1,2], [1,3], [2,3]]
输出: [2,3]
> 代码
class Solution {
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
vector<int> rp(1001);
int sz = edges.size();
// 初始化各元素为单独的集合,代表节点就是其本身
for(int i=0;i<sz;i++)
rp[i] = i;
for(int j=0;j<sz;j++){
// 找到边上两个节点所在集合的代表节点
int set1 = find(edges[j][0], rp);
int set2 = find(edges[j][1], rp);
if(set1 == set2) // 两个集合代表节点相同,说明出现环,返回答案
return edges[j];
else // 两个集合独立,合并集合。将前一个集合代表节点戳到后一个集合代表节点上
rp[set1] = set2;
}
return {0, 0};
}
// 查找路径并返回代表节点,实际上就是给定当前节点,返回该节点所在集合的代表节点
// 之前这里写的压缩路径,引起歧义,因为结果没更新到vector里,所以这里改成路径查找比较合适
// 感谢各位老哥的提议
int find(int n, vector<int> &rp){
int num = n;
while(rp[num] != num)
num = rp[num];
return num;
}
};