友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
684. 冗余连接
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-05-12 21:32:48
*/
public int[] findRedundantConnection(int[][] edges) {
int[] result = null;
UnionFind uf = new UnionFind(edges.length);
for (int[] edge : edges) {
int a = edge[0];
int b = edge[1];
int ap = uf.find(a);
int bp = uf.find(b);
if (ap == bp) {
result = edge;
}
uf.union(a, b);
}
return result;
}
private static class UnionFind {
private int[] parent;
public UnionFind(int n) {
parent = new int[n + 1];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
}
public int find(int a) {
List<Integer> path = new ArrayList<>();
while (a != parent[a]) {
path.add(a);
a = parent[a];
}
for (Integer x : path) {
parent[x] = a;
}
return a;
}
public void union(int a, int b) {
int ap = find(a);
int bp = find(b);
if (ap == bp) {
return;
}
if (ap < bp) {
parent[bp] = ap;
} else {
parent[ap] = bp;
}
}
}