Python嵌套列表处理：合并含共同元素子列表并去重

需要合并Python嵌套列表中所有包含至少一个共同元素的子列表，并去除重复项。示例如下：

示例输入：

foo = [
[0,1,2,6,9],
[0,1,2,6,5],
[3,4,7,3,2],
[12,36,28,73],
[537],
[78,90,34,72,0],
[573,73],
[99],
[41,44,79],
]

期望输出：

[
[0,1,2,6,9,5,3,4,7,78,90,34,72],
[12,36,28,73,573],
[537],
[99],
[41,44,79],
]

规则：只要子列表之间存在至少一个共同元素，就归为一组合并。

你当前的代码逻辑是基于子列表的索引i，寻找所有包含i的子列表并合并，这和需求完全不符——需求是子列表之间有共同元素就合并，而非按索引关联，因此无法得到正确结果。

这类合并连通分量的问题，用并查集是最高效的解决方案。核心思路是把有共同元素的子列表归为同一个集合，最终按集合分组合并。

实现代码 #

import json

def union_find_merge(lists):
    parent = {}
    
    # 查找元素的根节点，带路径压缩优化
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    
    # 合并两个元素所在的集合
    def union(x, y):
        x_root = find(x)
        y_root = find(y)
        if x_root != y_root:
            parent[y_root] = x_root
    
    # 初始化所有元素的父节点为自身
    for sublist in lists:
        for num in sublist:
            if num not in parent:
                parent[num] = num
        # 将当前子列表内的所有元素合并到同一集合
        if len(sublist) > 1:
            first = sublist[0]
            for num in sublist[1:]:
                union(first, num)
    
    # 按根节点分组，用集合自动去重
    groups = {}
    for num in parent:
        root = find(num)
        if root not in groups:
            groups[root] = set()
        groups[root].add(num)
    
    # 转换为列表格式，可选排序调整顺序
    result = [sorted(list(group)) for group in groups.values()]
    return result

# 加载数据并处理
if __name__ == "__main__":
    data = json.load(open('x.json'))
    merged = union_find_merge(data)
    json.dump(merged, open('out.json', 'w'), indent=4)

可选调整：保留元素出现顺序 #

如果需要保留元素在原列表中的出现顺序（而非排序），可以修改分组逻辑为：

# 按根节点分组并保留原始出现顺序
groups = {}
for sublist in lists:
    for num in sublist:
        root = find(num)
        if root not in groups:
            groups[root] = []
        if num not in groups[root]:
            groups[root].append(num)
result = list(groups.values())

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