684. 冗余连接
前言
「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。
这是本系列的第 7 篇题解，更多题解关注 Somnia1337@力扣。
题目描述
难度：🟡中等
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 n 个结点（结点值 1～n）的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges，edges[i] = [ai, bi] 表示图中在 ai 和 bi 之间存在一条边。
请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个结点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。
输入: edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
输出: [1,4]概念复习
- 简单图：无环、无平行边的图。
- 支：图的一个极大连通子图。
- 连通图：支的数量为 1 的图。
解题思路
「树」是一个无环无向的「连通图」，同时是一个「简单图」，因此在树中添加一条边之后一定会出现环。
遍历输入数组 edges 建图，此过程中，如果出现一条边，它使得其两个端点之间出现第 2 条道路，即出现了环，那么这条边就是要找的“冗余连接”。
通常用并查集维护结点之间的连通性，并查集在「数据结构与算法」学习过，简单概括就是：
- 查找：找结点所在的「支」
- 归并：将 2 个「支」合为 1 个
每个支用一个结点唯一代表，支可以看作等价类，代表结点就是代表元。
并查集初始化时，每个结点分别属于以自身代表的支，遍历 edges：
- 如果两个结点属于不同支，则在添加这条边之前，两个结点之间不连通，因此添加这条边不会产生环。添加它，然后合并两个支。
- 如果两个结点属于相同支，则在添加这条边之前，两个结点之间已连通，因此添加这条边会产生环，返回这条边。
复杂度
- 时间复杂度：，其中 为边数， 为反阿克曼函数，遍历时对 个结点进行路径压缩与按秩合并的复杂度为
- 空间复杂度：
代码
Java
class Solution {
public int[] findRedundantConnection(int[][] edges) {
int[] root = new int[edges.length + 1]; // 并查集
for (int i = 0; i <= edges.length; i++) root[i] = i;
for (int[] edge : edges) {
int n1 = edge[0], n2 = edge[1];
// 如果所属支不同, 则合为 1 个
if (find(root, n1) != find(root, n2)) union(root, n1, n2);
// 否则, 这条边将导致环, 返回
else return new int[]{n1, n2};
}
return null;
}
private int find(int[] root, int i) {
while (root[i] != i) {
root[i] = root[root[i]];
i = root[i];
}
return i;
}
private void union(int[] root, int x, int y) {
root[find(root, x)] = find(root, y);
}
}Python
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
def find(i: int) -> int:
if root[i] != i:
root[i] = find(root[i])
return root[i]
def union(n1, n2):
root[find(n1)] = find(n2)
n = len(edges)
root = list(range(n + 1)) # 并查集
for n1, n2 in edges:
# 如果所属支不同, 则合为 1 个
if find(n1) != find(n2):
union(n1, n2)
# 否则, 这条边将导致环, 返回
else:
return [n1, n2]
return []相关题目
685. 冗余连接 II
最后
更多系列「外源推文」&「生活分享」关注公众号：