如何合并嵌套列表中含公共元素的子列表并去重？

给定一个嵌套列表，要求将任意两个包含公共元素的子列表合并为一个无重复元素的子列表。例如输入[[0, 1], [3, 6], [3, 9]]，其中[3, 6]和[3, 9]共享元素3，合并后得到[3, 6, 9]，最终结果为[[0,1], [3, 6, 9]]。

以下是我尝试的代码，但无法正确解决问题：

for i in connected:
    for j in connected:
        a_set = set(i)
        b_set = set(j)
        if (a_set & b_set):
            i.extend(j)
            connected.remove(j)

原代码的问题 #

• 遍历中修改列表导致异常：循环过程中直接调用connected.remove(j)会改变原列表的长度和元素顺序，导致后续遍历跳过部分子列表，无法处理所有可能的合并情况。
• 未处理重复元素：i.extend(j)会将j的所有元素直接追加到i中，合并后的子列表会包含重复元素（比如例子中会得到[3,6,3,9]），不符合要求。
• 自合并无效操作：当i和j指向同一个子列表时，集合交集必然非空，会触发无意义的自扩展，进一步引入重复元素。

解决方案1：迭代合并法 #

通过维护已合并的集合列表，逐个处理每个子列表，合并所有有交集的集合：

def merge_overlapping_lists(connected):
    merged = []
    for sublist in connected:
        current = set(sublist)
        # 找出所有与当前子列表有交集的已合并集合
        to_merge_indices = []
        for idx, group in enumerate(merged):
            if current & group:
                to_merge_indices.append(idx)
        # 合并所有交集集合到当前集合
        for idx in reversed(to_merge_indices):
            current.update(merged.pop(idx))
        merged.append(current)
    # 转换回列表格式并返回
    return [list(group) for group in merged]

测试示例：

connected = [[0, 1], [3, 6], [3, 9]]
print(merge_overlapping_lists(connected))  # 输出: [[0, 1], [3, 6, 9]]

解决方案2：并查集（Union-Find）法 #

对于大规模数据，使用并查集算法效率更高，通过元素间的关联关系分组：

def merge_with_union_find(connected):
    parent = {}
    
    def find(x):
        # 查找根节点，带路径压缩
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    def union(x, y):
        # 合并两个元素所在的集合
        parent[find(x)] = find(y)
    
    # 初始化每个元素的父节点为自身
    for sublist in connected:
        if not sublist:
            continue
        first_elem = sublist[0]
        parent[first_elem] = first_elem
        for elem in sublist[1:]:
            parent[elem] = elem
            union(first_elem, elem)
    
    # 按根节点分组
    groups = {}
    for elem in parent:
        root = find(elem)
        groups.setdefault(root, []).append(elem)
    
    return list(groups.values())

测试示例：

connected = [[0, 1], [3, 6], [3, 9]]
print(merge_with_union_find(connected))  # 输出: [[0, 1], [3, 6, 9]]

内容的提问来源于stack exchange，提问作者Interference