友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
685. 冗余连接 II
在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组 edges。每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。
返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
示例 1：
输入：edges = [[1,2],[1,3],[2,3]] 输出：[2,3]
示例 2：
输入：edges = [[1,2],[2,3],[3,4],[4,1],[1,5]] 输出：[4,1]
提示：
-
n == edges.length -
3 <= n <= 1000 -
edges[i].length == 2 -
1 <= ui, vi <= n
思路分析
不仅仅并查集，还要考虑冲突和成不成环，多转了好几个弯。
| 看图示，还要再多思考思考。 |
-
一刷
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2026-05-13 19:48:26
*/
public int[] findRedundantDirectedConnection(int[][] edges) {
int n = edges.length;
UnionFind uf = new UnionFind(n + 1);
int[] parent = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
}
int conflict = -1;
int cycle = -1;
for (int i = 0; i < n; i++) {
int[] edge = edges[i];
int a = edge[0];
int b = edge[1];
if (parent[b] != b) {
conflict = i;
} else {
parent[b] = a;
int ap = uf.find(a);
int bp = uf.find(b);
if (ap == bp) {
cycle = i;
} else {
uf.union(a, b);
}
}
}
// 没有入度大于 1 的节点，即没有冲突，则有环
if (conflict < 0) {
return edges[cycle];
} else {
int[] edge = edges[conflict];
// 有环
if (cycle >= 0) {
return new int[]{parent[edge[1]], edge[1]};
} else {
// 没有环
return edge;
}
}
}
private static class UnionFind {
int[] ancestor;
public UnionFind(int n) {
ancestor = new int[n];
for (int i = 1; i < n; i++) {
ancestor[i] = i;
}
}
public int find(int a) {
List<Integer> path = new ArrayList<>();
while (a != ancestor[a]) {
path.add(a);
a = ancestor[a];
}
for (Integer p : path) {
ancestor[p] = 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) {
ancestor[bp] = ap;
} else {
ancestor[ap] = bp;
}
}
}