冗余连接

难度: Medium

树可以看成是一个连通且无环的无向图。

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [a_i, b_i] 表示图中在 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 中无重复元素
给定的图是连通的

注意：本题与主站 684 题相同： https://leetcode-cn.com/problems/redundant-connection/

Submission

运行时间: 26 ms

内存: 16.4 MB

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges)
        f = list(range(n))
        def find(x):
            if x == f[x]:
                return x
            f[x] = find(f[x])
            return f[x]

        def merge(edges):
            n = len(edges)
            for i in range(n):
                m, n = edges[i][0], edges[i][1]
                f1, f2 = find(m-1), find(n-1)
                if f1 == f2:
                    dele = edges[i]
                else:
                    f[f1] = f2
            return f, dele
        f, dele = merge(edges)
        return dele

Explain

该题解使用了并查集的数据结构来找出导致图中出现环的多余边。并查集主要用于处理一些不相交集合的合并及查询问题。这里，每个节点最初指向自己，表示它们各自是一个独立的集合。题解过程中，对于每一条边，使用 find 函数来查找每个顶点的根节点。如果两个顶点的根节点相同，说明添加这条边会形成环，因此这条边就是多余的。否则，通过 merge 函数将这两个顶点所在的集合合并。题目要求返回最后出现在数组中的多余的边，因此在发现多余的边时保存下来，直至所有边检查完毕。

时间复杂度: O(n)

空间复杂度: O(n)

# 定义解答类

class Solution:
    def findRedundantConnection(self, edges: List[List[int]]) -> List[int]:
        n = len(edges) # 获取边的数量
        f = list(range(n)) # 初始化并查集
        
        def find(x):
            if x == f[x]:
                return x # 路径压缩前的根节点查找
            f[x] = find(f[x]) # 路径压缩
            return f[x]

        def merge(edges):
            n = len(edges)
            dele = [] # 初始化删除的边
            for i in range(n):
                m, n = edges[i][0], edges[i][1]
                f1, f2 = find(m-1), find(n-1) # 查找两个顶点的根节点
                if f1 == f2: # 如果根节点相同，说明形成环
                    dele = edges[i] # 记录这条多余的边
                else:
                    f[f1] = f2 # 合并两个集合
            return f, dele
        
        f, dele = merge(edges) # 执行合并查找
        return dele # 返回多余的边

Explore

路径压缩是并查集优化技术之一，其目的是减少树的高度，从而使得未来查找根节点的操作更快。在路径压缩过程中，我们使每个访问过的节点直接指向其根节点。这样，经过几次操作后，树的高度大幅度减小，使得任何节点到根节点的路径都将大大缩短，从而提高查找效率。具体来说，路径压缩可以将并查集的时间复杂度几乎降至接近常数时间，这对于处理大量集合合并及查询操作的场景非常关键，显著提升算法性能。

按秩合并是另一种并查集的优化方式，通过记录集合的'秩'（通常是树的高度或者节点数量），并总是将秩较小的集合合并到秩较大的集合上。这样可以避免形成高度不平衡的树，从而进一步优化查找效率。题解没有实现按秩合并，可能会导致树的高度增加，从而影响算法的最优性能。要实现按秩合并，我们可以增加一个数组来记录每个节点的秩，然后在合并时，比较两个根节点的秩，总是将秩较小的树合并到秩较大的树上。如果秩相同，则选择一个作为根，并将其秩加一。

题解中确实处理了从1开始的节点编号到从0开始的数组索引的转换。在`merge`函数中，每次处理边的时候，用`edges[i][0]`和`edges[i][1]`表示的是从1开始的节点编号，而在查找节点根时，通过`find(m-1)`和`find(n-1)`转换为从0开始的索引。这种转换是准确的，因为数据结构的数组`f`是从0索引开始的，而节点编号从1开始，所以需要减1来对应到正确的数组索引。这样处理确保了节点编号与内部索引之间的一致性。