解题思路
题意要求将多个实体匹配系统输出的实体结果进行去重、合并与排序。
每个系统的输出可视为一个集合,若两个集合存在交集,则它们应被合并为一个更大的集合。
这实际上是一个并查集(Union-Find) 的典型应用场景:
- 每个实体可以看作一个节点;
- 若两个实体在同一系统结果中出现,则它们属于同一连通分量;
P4343.第2题-实体匹配结果合并问题
题目内容
某业务部门有多个数据来源,现在需要对多个来源的实体数据进行去重、消歧、合并。有多个实体匹配系统(假设系统的匹配结果完全正确),每个系统从不同角度进行匹配,匹配结果是相同实体列表。
这些匹配结果中往往存在交叉重复的问题,需要对所有匹配结果进行合并去重。例如系统 A 的匹配结果是 ["1", "2"] ,系统 B 的匹配结果是 ["2", "3"],那么合并后的匹配结果是 ["1", "2", "3"]。请你按照上述逻辑,编写代码实现对匹配结果的合并去重。
输入描述
输出描述
输出 M 行(M<=N),每行内容是合并后的匹配结果。
注意,每行的输出结果需要按照字典顺序进行排序;合并后的匹配结果列表之间,也需要按字典顺序进行排序。
样例1
输入
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";
另外两组结果与其他组不存在重复;
合并后的匹配结果列表之间,按字典序排序后输出,即样例输出所示内容。
样例2
输入
2
1 2
2 3
输出
1 2 3
说明
有两组匹配结果,即 "1 2"和"2 3",存在重复实体 "2",故可以合并为 "1 2 3"。