难度: Medium
树可以看成是一个连通且 无环 的 无向 图。
给定往一棵 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.length3 <= n <= 1000edges[i].length == 21 <= ai < bi <= edges.lengthai != biedges 中无重复元素运行时间: 22 ms
内存: 16.3 MB
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
parent = list(range(len(edges)+1))
def find(node: int) -> int:
while parent[node] != node:
node = parent[node]
return node
for u, v in edges:
parent[u] = find(u)
parent[v] = find(v)
if parent[u] != parent[v]:
parent[parent[u]] = parent[v]
else:
return [u, v]
本题解使用了并查集算法。我们遍历每条边，将边的两个顶点所在的连通分量进行合并。如果遇到一条边的两个顶点已经属于同一个连通分量，那么说明这条边的出现会导致环路，因此它就是我们要找的那条多余的边。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution:
def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
# 初始化并查集，每个节点的父节点初始为自身
parent = list(range(len(edges)+1))
# 并查集的查找函数，用于查找一个节点所在连通分量的根节点
def find(node: int) -> int:
# 沿着父节点指针一路向上查找，直到找到根节点
while parent[node] != node:
node = parent[node]
return node
# 遍历每一条边
for u, v in edges:
# 查找 u 所在连通分量的根节点
parent[u] = find(u)
# 查找 v 所在连通分量的根节点
parent[v] = find(v)
# 如果 u 和 v 不属于同一个连通分量，则将它们合并
if parent[u] != parent[v]:
parent[parent[u]] = parent[v]
# 如果 u 和 v 已经属于同一个连通分量，则说明这条边导致了环路，将其作为答案返回
else:
return [u, v]
并查集是一种特殊的数据结构，用于高效地处理动态连通性问题。在处理图的冗余连接问题时，我们可以利用并查集来跟踪每个顶点所属的连通分量。通过遍历图中的每条边，我们尝试将边的两个顶点合并到同一个连通分量中。如果在尝试合并前，两个顶点已经属于同一连通分量，这表明添加这条边会形成一个环，因此这条边就是冗余的。这种方法有效地利用了并查集维护连通分量的特性，可以在较低的时间复杂度内判断并找出图中的冗余连接。
路径压缩是并查集优化技术之一，主要用来减少查找根节点时的时间复杂度。具体来说，路径压缩在每次查找过程中，将查找路径上的每个节点直接连接到根节点。这样做的结果是，未来对同一连通分量内任一节点的查找操作都可以更快地到达根节点，因为路径被大大缩短了。通过路径压缩，可以将并查集的时间复杂度优化到接近常数时间，从而提高整个算法的效率。
是的，这种处理方法总是有效的。在题目设定中，图中只有一个冗余连接，这意味着图是一个几乎是树的结构，只多了一条边导致成环。因此，当我们按顺序处理边时，最后一个在并查集中检测到已经处于同一连通分量的边，必定是导致环的冗余边。因为如果先出现的边是冗余的，那么后面的边就不会形成环。所以，按照题解的方法处理，总能正确返回最后出现的那个冗余连接。
在并查集中，每个节点初始化为自己是父节点的目的在于表示每个节点最初是独立的连通分量。这种初始化方式简单且直观，表明在开始时，没有任何两个节点是相连的，即每个节点自成一个连通分量。随着算法的进行，某些节点会被合并到同一个连通分量中，但初始化时，每个节点作为自己的父节点是表示它们的独立性和初始状态。这是并查集构建其数据结构的基础。