笔试时间：2025年10月29日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：实体匹配结果合并问题

某业务部门有多个数据来源，现在需要对多个来源的实体数据进行去重、消歧、合并。有多个实体匹配系统（假设系统的匹配结果完全正确），每个系统会从不同角度进行匹配，匹配结果是相同实体列表。

这些匹配结果中往往存在交叉重复的问题，需要对所有匹配结果进行合并去重。例如系统A的匹配结果是 [1,2,3]，系统B的匹配结果是 [2,3,4]，那么合并后的匹配结果是 [1,2,3,4]。请你按照上述逻辑，编写代码实现对匹配结果的合并去重。

输入描述

输出描述

输出 M 行（M ≤ N），每行内容是合并后的匹配结果。

注意：

• 每行的输出结果需要按照字典序进行排序
• 合并后的匹配结果列表之间，也需要按字典序进行排序

样例输入

5

1 2 3

4 5

11 22

33 44 55 1

3 66

样例输出

1 2 3 33 44 55 66

11 22

4 5

解释：

匹配结果"1 2 3"、"33 44 55 1"、"3 66"，存在重复实体"1"和"3"，故可以合并，合并后按字典序为"1 2 3 33 44 55 66"；另外两组结果与其他组不存在重复；合并后的匹配结果列表之间，按字典序排序后输出，即样例输出所示内容。

参考题解

这个问题本质上是合并具有公共元素的集合，属于典型的并查集应用场景。

核心思路

1. 问题转化：将每个匹配结果视为一个集合，如果两个集合有公共元素，说明它们应该合并
2. 关键观察：如果实体A和B在同一行，实体B和C在同一行，那么A、B、C应该属于同一个实体组
3. 算法选择：使用并查集来高效处理集合合并操作

Python：

import sys
from collections import defaultdict

sys.setrecursionlimit(200000)

parent = {}

def find(i):
    if i not in parent:
        parent[i] = i
        return i
    if parent[i] == i:
        return i
    parent[i] = find(parent[i])
    return parent[i]

def union(i, j):
    root_i = find(i)
    root_j = find(j)
    if root_i != root_j:
        parent[root_i] = root_j

def solve():
    n = int(sys.stdin.readline())
    lines_to_process = []
    
    for _ in range(n):
        entities = sys.stdin.readline().split()
        lines_to_process.append(entities)
        for entity in entities:
            if entity not in parent:
                parent[entity] = entity
    
    for entities in lines_to_process:
        first_entity = entities[0]
        for i in range(1, len(entities)):
            union(first_entity, entities[i])
    
    groups = defaultdict(set)
    for entity in parent:
        root = find(entity)
        groups[root].add(entity)
    
    final_merged_lists = []
    for group_set in groups.values():
        sorted_group = sorted(list(group_set))
        final_merged_