如何基于关联关系对列表中的单词对进行分组？

Hey there! This is a classic connected components problem—think of each word as a node in a graph, and each word pair as an edge connecting two nodes. We need to group all nodes that are linked directly or indirectly, which is exactly what the Union-Find (Disjoint Set Union, DSU) data structure is perfect for. Here's how you can implement it in Python:

实现步骤 #

1. 定义并查集类 #

This class handles two core operations: find (to locate the root of a node with path compression for efficiency) and union (to merge two sets by rank to keep the tree structure shallow).

class UnionFind:
    def __init__(self):
        self.parent = {}
        self.rank = {}
    
    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):
        # 先找到两个节点的根节点
        root_x = self.find(x)
        root_y = self.find(y)
        
        if root_x == root_y:
            return  # 已经在同一组，无需重复合并
        
        # 按秩合并：把秩较小的树合并到秩较大的树上，保持结构平衡
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        else:
            self.parent[root_y] = root_x
            if self.rank[root_x] == self.rank[root_y]:
                self.rank[root_x] += 1

2. 处理输入并生成分组 #

We'll initialize the Union-Find structure with all unique words from the input pairs, merge each pair, and finally group words by their root node.

# 输入的单词对列表
word_pairs = [('airplane', 'ship'), ('car', 'truck'), ('bird', 'dog'), ('cat', 'horse'), ('cat', 'monkey'), ('dog', 'cat'), ('dog', 'deer'), ('horse', 'dog'), ('horse', 'monkey'), ('deer', 'cat'), ('deer', 'horse'), ('monkey', 'bird'), ('monkey', 'dog'), ('monkey', 'deer')]

# 初始化并查集
uf = UnionFind()
all_words = set()
for pair in word_pairs:
    all_words.add(pair[0])
    all_words.add(pair[1])

# 给每个单词初始化父节点和秩
for word in all_words:
    uf.parent[word] = word
    uf.rank[word] = 0

# 合并每一对单词
for x, y in word_pairs:
    uf.union(x, y)

# 整理分组结果
groups = {}
for word in all_words:
    root = uf.find(word)
    if root not in groups:
        groups[root] = []
    groups[root].append(word)

# 转换为目标列表格式
result = list(groups.values())
print(result)

3. 运行结果 #

When you run this code, you'll get exactly the expected output:

[['airplane', 'ship'], ['car', 'truck'], ['monkey', 'bird', 'dog', 'deer', 'cat', 'horse']]

为什么这个方法有效？ #

• The Union-Find structure efficiently tracks which nodes belong to the same set, even as we merge more pairs.
• Path compression and union by rank ensure that operations are nearly constant time, making this approach scalable even for larger datasets.

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