编写函数统计元组集合中关联数字联合组的数量

需求说明 #

• 输入：一个元组集合
• 输出：元组集合中关联数字联合组的数量（关联规则：若两个元组包含共同数字则归为同一组；间接关联的元组也属于同一组）

示例1 #

# 输入
{(0, 1), (3, 4), (0, 0), (1, 1), (3, 3), (2, 2), (1, 0)}

# 预期输出: 3

分组说明 #

• (3,4) 和 (3,3) 共享数字3，算作1组
• (0, 1)、(0, 0)、(1, 1)、(1, 0) 通过数字0或1相互关联，算作1组
• (2, 2) 无关联元组，算作1组
  总计：1+1+1=3

示例2 #

# 输入
{(0, 1), (2, 1), (0, 0), (1, 1), (0, 3), (2, 0), (0, 2), (1, 0), (1, 3)}

# 预期输出: 1

分组说明 #

所有元组通过包含的共同数字形成间接关联，整体算作1组

解决方案：并查集（Union-Find）实现 #

这个问题本质是求图的连通分量数量：将每个数字视为节点，每个元组中的两个数字（含相同数字）代表一条边，连通的节点构成一个组，最终统计独立连通分量的总数即可。

class UnionFind:
    def __init__(self):
        self.parent = {}
    
    def find(self, x):
        if x not in self.parent:
            self.parent[x] = x
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

def count_connected_groups(tuples_set):
    uf = UnionFind()
    # 合并每个元组内的两个数字
    for a, b in tuples_set:
        uf.union(a, b)
    # 收集所有出现过的数字的根节点
    all_numbers = set()
    for a, b in tuples_set:
        all_numbers.update((a, b))
    return len({uf.find(num) for num in all_numbers})

# 测试示例1
test1 = {(0, 1), (3, 4), (0, 0), (1, 1), (3, 3), (2, 2), (1, 0)}
print(count_connected_groups(test1))  # 输出3

# 测试示例2
test2 = {(0, 1), (2, 1), (0, 0), (1, 1), (0, 3), (2, 0), (0, 2), (1, 0), (1, 3)}
print(count_connected_groups(test2))  # 输出1

代码说明 #

1. UnionFind类：实现路径压缩和合并操作，高效维护节点的连通关系
2. count_connected_groups函数：
   • 初始化并查集实例
   • 遍历输入元组，合并每个元组内的两个数字
   • 收集所有出现过的数字，统计其根节点的唯一数量，即为所求的组数量

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