实体匹配结果归并与排序

题目分析

本题的核心是集合合并问题：多个匹配引擎各自输出一组被认为是同一实体的编号，如果两组编号之间有交集，就应该合并为一个更大的集合。最终对所有合并后的集合进行去重、排序并输出。

思路

并查集（Union-Find）

这是一道经典的并查集应用题。

1. 建模：将每个编号视为一个节点。对于同一行中出现的所有编号，将它们两两合并到同一个集合中（实际只需将后续元素与第一个元素合并即可）。
2. 合并：由于并查集的传递性，如果第 4 行有 {7, 8, 9} 且第 6 行有 {9, 11}，因为 9 是公共元素，这两行的所有元素会自动归入同一个集合。
3. 收集结果：遍历所有节点，按其根节点分组，得到最终的若干合并集合。
4. 排序输出：

- 每个集合内部：按字符串字典序升序排列

- 集合之间：将每个集合视为一个字符串序列，按字典序排列

关键细节

• 编号是字符串，排序时使用字符串字典序（例如 "11" < "7"，因为字符 '1' < '7'）。
• 同一行内可能有重复编号（如 7 7 8 9），需要去重。
• 并查集使用路径压缩优化，保证效率。

代码

import sys
from collections import defaultdict

def main():
    input_data = sys.stdin.read().split('\n')
    idx = 0
    n = int(input_data[idx]); idx += 1

    parent = {}

    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb

    for i in range(n):
        line = input_data[idx].strip() if idx < len(input_data) else ""
        idx += 1
        nums = line.split()
        seen = set()
        unique = []
        for x in nums:
            if x not in seen:
                seen.add(x)
                unique.append(x)
                if x not in parent:
                    parent[x] = x
        for j in range(1, len(unique)):
            union(unique[0], unique[j])

    # 按根节点分组收集
    clusters = defaultdict(set)
    for x in parent:
        clusters[find(x)].add(x)

    # 组内字典序排序，组间字典序排序
    result = []
    for members in clusters.values():
        result.append(sorted(members))
    result.sort()

    for line in result:
        print(' '.join(line))

main()

复杂度分析

设所有编号总数为 ，去重后唯一编号数为 。

• 时间复杂度：，其中 是反阿克曼函数（并查集操作近似常数），排序部分为 。
• 空间复杂度：，用于存储并查集和分组结果。