LeetCode 685. 冗余连接 II
题目描述
题意分析
有根有向树中，根的入度为零，其余节点各有一个父节点，且都能从根到达。输入是在这样一棵树上增加一条有向边得到的，要求删除一条边恢复有根树；若多条边都能删除，返回输入下标最大的那条。
新边只会让它的终点多一个父节点，所以至多有一个节点入度变成二。若出现双父节点，必须删掉它的两条入边之一；若没有双父节点，则需要从新增的环上删边。先处理入度，才能正确使用并查集判断剩余结构。
解法：识别双父节点，再跳边判环
核心思路
[!blue]
incoming[v]保存节点v第一条入边的下标，初始为-1，以免与合法的下标零混淆。再次遇到指向同一节点的边时，把先、后两条入边下标记为first、second。它们是仅有的删除候选，因为删除别处的边无法消除这个节点的双父关系。有双父节点时，优先尝试跳过较晚的
second，再用并查集检查剩下的边。parent、size维护的是无向连通块，不是原有向图中的父子关系；一条边的两端已经同属一个连通块时，再加入它就会产生无向环。跳过
second后，每个节点入度至多为一，并且恰好剩下n-1条边。若没有无向环，这些边必定连接全部n个节点；入度之和又是n-1，因此恰好一个节点入度为零。沿父节点回溯不会遇到环，只能到达这个唯一根，所以剩下的图确实是一棵有根有向树。此时删除second合法，而且它比另一候选更靠后。若跳过
second后仍检测到环，删除它不能恢复树。候选只有first、second，题目又保证一定能删一条边恢复原树，因此必须返回first，不应返回刚检测到的那条闭环边。没有双父节点时，不跳过任何边。原树加一条边后，忽略方向的图恰有一个环；此时所有节点入度都是一，删掉任意环边都能恢复唯一根和树结构。按输入顺序合并时，环上最后出现的边才会让两端已经连通，因此首次合并失败的当前边，正是题目要求的最靠后可删边。
代码末尾只在“跳过
second后始终无环”时才会执行return edges[second]。没有双父的情况必定在扫描中检测到环并提前返回，不会拿-1当作最终下标。
解题步骤
- 扫描所有边，记录各节点的第一条入边，定位可能的
first、second。- 初始化并查集，按原输入顺序处理边；若存在
second，暂时跳过它。- 两端已经连通时，存在双父就返回
first，否则返回当前边。- 没有检测到环时返回
second；合并不同连通块时按大小连接，并在查找中压缩路径。
代码实现
class Solution {
public int[] findRedundantDirectedConnection(int[][] edges) {
int n = edges.length;
int first = -1;
int second = -1;
int[] incoming = new int[n + 1];
Arrays.fill(incoming, -1);
for (int i = 0; i < n; i++) {
int child = edges[i][1];
if (incoming[child] >= 0) {
first = incoming[child];
second = i;
} else {
incoming[child] = i;
}
}
int[] parent = new int[n + 1];
int[] size = new int[n + 1];
for (int i = 1; i <= n; i++) {
parent[i] = i;
size[i] = 1;
}
for (int i = 0; i < n; i++) {
if (i == second) {
continue;
}
int a = find(parent, edges[i][0]);
int b = find(parent, edges[i][1]);
if (a == b) {
return edges[first >= 0 ? first : i];
}
if (size[a] < size[b]) {
int t = a;
a = b;
b = t;
}
parent[b] = a;
size[a] += size[b];
}
return edges[second];
}
private int find(int[] parent, int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
}
func findRedundantDirectedConnection(edges [][]int) []int {
n := len(edges)
first, second := -1, -1
incoming := make([]int, n+1)
for i := range incoming {
incoming[i] = -1
}
for i, edge := range edges {
child := edge[1]
if incoming[child] >= 0 {
first, second = incoming[child], i
} else {
incoming[child] = i
}
}
parent, size := make([]int, n+1), make([]int, n+1)
for i := 1; i <= n; i++ {
parent[i] = i
size[i] = 1
}
find := func(x int) int {
for parent[x] != x {
parent[x] = parent[parent[x]]
x = parent[x]
}
return x
}
for i, edge := range edges {
if i == second {
continue
}
a, b := find(edge[0]), find(edge[1])
if a == b {
if first >= 0 {
return edges[first]
}
return edge
}
if size[a] < size[b] {
a, b = b, a
}
parent[b] = a
size[a] += size[b]
}
return edges[second]
}
复杂度分析
- 时间复杂度：$O(n\alpha(n))$。第一遍扫描入边为 $O(n)$，第二遍使用按大小合并和路径压缩的并查集处理每条边，$\alpha$ 为反阿克曼函数。
- 空间复杂度：$O(n)$，用于入边记录及并查集数组。输入边数组不被修改。
关键点总结
[!green]
- “有根树加一条边”的保证，使异常仅有双父和环这几种组合，不能把本方法直接当作任意有向图的判树算法。
- 并查集只检查无向环；结合已修正的入度条件和
n-1条边，才足以证明剩余图是有根树。- 有双父时先尝试删除较晚入边，无双父时选择唯一环上最晚出现的边，两者分别满足靠后优先规则。
易错点总结
[!yellow]
- 直接对全部边套无向判环，可能选到无法消除双父关系的边。
- 跳过
second后仍有环时，要删first；不能继续返回second或当前闭环边。incoming存的是原边下标，初值必须区别于零；并查集的parent也不能用来替代这个入边记录。- 选择较晚候选后仍要验证剩余结构，不能仅凭下标靠后就直接删掉它。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 684. 冗余连接 | 中等 | 从无向冗余边扩展到有向树，必须先识别并处理入度为 2 的节点。 |
| 261. 以图判树 | 中等 | 删去候选边后的目标都是一棵树；本题还要求有向父子关系及靠后边规则。 |