合并含共同元素的子列表问题求助（3D几何连通性场景）

方法一：并查集（Union-Find） #

这是处理连通性问题的经典方案，适合大规模数据场景，效率更高。

class UnionFind:
    def __init__(self):
        self.parent = {}
    
    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):
        # 初始化元素父节点为自身
        if x not in self.parent:
            self.parent[x] = x
        if y not in self.parent:
            self.parent[y] = y
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

# 处理输入列表
input_list = [[3, 0], [0, 9], [9, 13], [7, 4]]
uf = UnionFind()

# 遍历子列表合并元素
for pair in input_list:
    uf.union(pair[0], pair[1])

# 按根节点分组
groups = {}
for num in uf.parent:
    root = uf.find(num)
    groups.setdefault(root, []).append(num)

# 转换为结果列表（排序可选）
result = [sorted(group) for group in groups.values()]
print(result)  # 输出: [[0, 3, 9, 13], [4, 7]]

方法二：集合迭代合并 #

适合小规模数据，逻辑直观，无需额外数据结构。

input_list = [[3, 0], [0, 9], [9, 13], [7, 4]]
sets = [set(sublist) for sublist in input_list]
i = 0
while i < len(sets):
    current = sets[i]
    j = i + 1
    while j < len(sets):
        if current & sets[j]:  # 存在交集则合并
            current.update(sets[j])
            del sets[j]
        else:
            j += 1
    i += 1

# 转换为排序后的列表
result = [sorted(s) for s in sets]
print(result)  # 输出: [[0, 3, 9, 13], [4, 7]]

说明 #

• 两种方法都能得到符合要求的结果，排序为可选操作，可根据需求调整。
• 并查集时间复杂度接近O(n)，适合处理大量子列表；迭代合并实现简单，但时间复杂度较高，适合小数据量场景。

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