使用并查集（Union-Find）高效实现数组间连通ID分组-Python教程-PHP中文网

使用并查集（Union-Find）高效实现数组间连通ID分组

本文介绍如何将含重叠元素的多个字符串数组合并为逻辑连通组，并为每个唯一id分配统一组标签——核心是建模为图的连通分量问题，推荐采用并查集（union-find）结构求解，比迭代合并更鲁棒、时间复杂度更低。

本文介绍如何将含重叠元素的多个字符串数组合并为逻辑连通组，并为每个唯一id分配统一组标签——核心是建模为图的连通分量问题，推荐采用并查集（union-find）结构求解，比迭代合并更鲁棒、时间复杂度更低。

该问题本质是连通性聚类（Connected Component Clustering）：每个数组可视为一个“团”（clique），其中所有元素两两连通；若两个数组存在至少一个公共元素，则它们所属的所有元素应被归入同一组。这等价于在无向图中求连通分量——节点是所有唯一ID，边由数组内部隐式全连接（即每数组内任两ID间添加边），最终对图做连通分量分析。

虽然原始答案提供了基于迭代合并的启发式方法（reduceMatrix），但它存在明显缺陷：

仅执行两次合并，无法保证收敛（例如链式依赖 A-B, B-C, C-D 需多轮传递）；
时间复杂度不稳定，最坏情况下需 O(n²) 轮扫描；
未去重，易导致重复插入与逻辑错误（如 findAndAdd 中二次遍历 arr 并重复 append 可能引入冗余元素）。

✅ 推荐方案：并查集（Union-Find）
并查集专为动态连通性设计，支持高效 union（合并集合）与 find（查询根节点），时间复杂度接近 O(α(n))（α 为反阿克曼函数，实践中可视作常数）。

以下是完整、健壮、可直接运行的 Python 实现：

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}

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

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return
        # 按秩合并
        if self.rank[px] <p><strong>输出结果：</strong></p><pre class="brush:php;toolbar:false;">A, Group 2
C, Group 2
D, Group 2
E, Group 1
F, Group 2
I, Group 1
J, Group 2
L, Group 2
O, Group 1
P, Group 1
Q, Group 1
R, Group 1
S, Group 2
V, Group 2
W, Group 1
X, Group 2
Z, Group 2

✅ 关键优势说明：