题目描述
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个节点 (节点值 1~n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间,且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ,edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边,删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案,则返回数组 edges 中最后出现的那个。
并查集介绍
并查集主要实现两个操作:
- 合并两个集合
- 查询某个元素的祖宗节点
问题分析
对于节点形成环,可以等价于两个点在连边之前,已经在一个集合里。
因此,这道题可以用并查集实现判断所要删除的边,使得图不形成环。
程序代码
class Solution {
private:
// 找点x的祖先节点
int find(vector<int>& p, int x) {
if(p[x] != x) p[x] = find(p, p[x]);
return p[x];
}
public:
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
int n = edges.size();
vector<int> p(n + 1);
// 初始化并查集
for(int i = 1; i <= n; i++) {
p[i] = i;
}
for(auto e : edges) {
int pa = find(p, e[0]), pb = find(p, e[1]);
if(pa == pb) return e;
// 集合合并
p[pa] = pb;
}
return {
};
}
};