684. 冗余连接

#python #leetcode #union-find #acyclic-undirected-graph

题目描述¶

关联：https://leetcode.cn/problems/redundant-connection/description

题目描述

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

给定往一棵 n 个节点 (节点值 1～n) 的树中添加一条边后的图。添加的边的两个顶点包含在 1 到 n 中间，且这条附加的边不属于树中已存在的边。图的信息记录于长度为 n 的二维数组 edges ，edges[i] = [a_i, b_i] 表示图中在 a_i 和 b_i 之间存在一条边。

请找出一条可以删去的边，删除后可使得剩余部分是一个有着 n 个节点的树。如果有多个答案，则返回数组 edges 中最后出现的那个。

范围：

\(n == \text{edges.length}\)
\(3 \leq n \leq 1000\)
\(\text{edges}[i].\text{length} == 2\)
\(1 \leq a_i < b_i \leq \text{edges.length}\)
\(a_i \neq b_i\)
\(\text{edges}\) 中无重复元素
给定的图是连通的

解题思路¶

并查集秒了。

可以使用并查集（Union-Find）数据结构来解决在图中找到冗余连接的问题。并查集可以高效地管理和合并不相交的集合，并且可以用来检测无向图中的环。

步骤：

初始化并查集：创建一个父节点数组来跟踪每个节点的父节点，并创建一个秩数组来优化树的高度。
处理每条边：对于每条边，使用并查集检查这条边的两个节点是否已经连接。
- 如果已经连接，说明添加这条边会形成环，因此这条边就是冗余边。
- 如果没有连接，则将这两个节点合并。
返回冗余边：第一个形成环的边就是冗余边。

完整题解¶

UnionFind 类：管理并查集的合并和查找操作，使用路径压缩和按秩合并来提高效率。

findRedundantConnection 方法：遍历每条边，使用并查集检测第一个形成环的边。

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))  # 父节点
        self.rank = [1] * size  # 秩

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.parent[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.parent[rootX] = rootY
            else:
                self.parent[rootY] = rootX
                self.rank[rootX] += 1
            return True
        return False

class Solution:
    def findRedundantConnection(self, edges: list[list[int]]) -> list[int]:
        n = len(edges)
        uf = UnionFind(n + 1)  # 初始化并查集，节点编号从1到n
        for edge in edges:
            if not uf.union(edge[0], edge[1]):
                return edge

复杂度分析¶

时间复杂度：\(O(E \cdot \alpha(E))\)，其中 \(E\) 是边的数量，\(\alpha\) 是 Ackermann 函数的反函数，可以看作是一个很小的常数。在并查集的操作中，find 和 union 的时间复杂度均为 \(O(\alpha(E))\)。
空间复杂度：\(O(E)\)。因为创建的父节点数组和秩数组的长度都为 \(E\)。

684. 冗余连接

题目描述¶

解题思路¶

完整题解¶

复杂度分析¶

评论