如何从两列数据中提取图形关联的唯一值？

输入数据 #

原始两列关联数据：

其中的关联逻辑为节点间的连通关系（重复条目不影响最终连通性）：

• 1 ↔ 5
• 5 ↔ 2
• 2 ↔ 1
• 1 ↔ 4
• 4 ↔ 8

期望输出 #

提取所有相互连通的节点（孤立节点3、10无关联，故排除），得到唯一值集合：

解决方案：并查集（Union-Find）算法处理连通分量 #

这类问题本质是找图的连通分量，用并查集算法可以高效解决，以下是Python实现：

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

# 加载输入数据
data_pairs = [(1,5), (2,1), (3,10), (4,8), (1,4), (1,5), (2,5)]

# 初始化并查集并合并所有关联对
uf = UnionFind()
for a, b in data_pairs:
    uf.union(a, b)

# 分组所有节点到对应的连通分量
components = {}
for node in uf.parent:
    root = uf.find(node)
    components.setdefault(root, []).append(node)

# 提取包含节点最多的连通分量（即目标集合）
target_nodes = sorted(max(components.values(), key=len))

# 输出结果
print("输出唯一关联值：")
for num in target_nodes:
    print(num)

运行代码后输出：

1
2
4
5
8

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