树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 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]
示例 2:
输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]] 输出: [1,4]
提示:
n == edges.length
3 <= n <= 1000
edges[i].length == 2
1 <= ai < bi <= edges.length
ai != bi
edges
中无重复元素- 给定的图是连通的
并查集。
模板 1——朴素并查集:
# 初始化,p存储每个点的父节点
p = list(range(n))
# 返回x的祖宗节点
def find(x):
if p[x] != x:
# 路径压缩
p[x] = find(p[x])
return p[x]
# 合并a和b所在的两个集合
p[find(a)] = find(b)
模板 2——维护 size 的并查集:
# 初始化,p存储每个点的父节点,size只有当节点是祖宗节点时才有意义,表示祖宗节点所在集合中,点的数量
p = list(range(n))
size = [1] * n
# 返回x的祖宗节点
def find(x):
if p[x] != x:
# 路径压缩
p[x] = find(p[x])
return p[x]
# 合并a和b所在的两个集合
if find(a) != find(b):
size[find(b)] += size[find(a)]
p[find(a)] = find(b)
模板 3——维护到祖宗节点距离的并查集:
# 初始化,p存储每个点的父节点,d[x]存储x到p[x]的距离
p = list(range(n))
d = [0] * n
# 返回x的祖宗节点
def find(x):
if p[x] != x:
t = find(p[x])
d[x] += d[p[x]]
p[x] = t
return p[x]
# 合并a和b所在的两个集合
p[find(a)] = find(b)
d[find(a)] = distance
对于本题,先遍历所有的边,如果边的两个节点已经属于同个集合,说明两个节点已经相连,若再将这条件加入集合中,就会出现环,因此可以直接返回这条边。
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
def find(x):
if p[x] != x:
p[x] = find(p[x])
return p[x]
p = list(range(1010))
for a, b in edges:
if find(a) == find(b):
return [a, b]
p[find(a)] = find(b)
return []
class Solution {
private int[] p;
public int[] findRedundantConnection(int[][] edges) {
p = new int[1010];
for (int i = 0; i < p.length; ++i) {
p[i] = i;
}
for (int[] e : edges) {
int a = e[0], b = e[1];
if (find(a) == find(b)) {
return e;
}
p[find(a)] = find(b);
}
return null;
}
private int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
}
class Solution {
public:
vector<int> p;
vector<int> findRedundantConnection(vector<vector<int>>& edges) {
p.resize(1010);
for (int i = 0; i < p.size(); ++i) p[i] = i;
for (auto& e : edges) {
int a = e[0], b = e[1];
if (find(a) == find(b)) return e;
p[find(a)] = find(b);
}
return {};
}
int find(int x) {
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
};
func findRedundantConnection(edges [][]int) []int {
p := make([]int, 1010)
for i := range p {
p[i] = i
}
var find func(x int) int
find = func(x int) int {
if p[x] != x {
p[x] = find(p[x])
}
return p[x]
}
for _, e := range edges {
a, b := e[0], e[1]
if find(a) == find(b) {
return e
}
p[find(a)] = find(b)
}
return []int{}
}
/**
* @param {number[][]} edges
* @return {number[]}
*/
var findRedundantConnection = function (edges) {
let p = Array.from({ length: 1010 }, (_, i) => i);
function find(x) {
if (p[x] != x) {
p[x] = find(p[x]);
}
return p[x];
}
for (let [a, b] of edges) {
if (find(a) == find(b)) {
return [a, b];
}
p[find(a)] = find(b);
}
return [];
};