首页 > 试题广场 >

实体匹配结果归并与排序

[编程题]实体匹配结果归并与排序

热度指数：40 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在数据治理平台中，不同的实体匹配引擎会各自产出“被认为指向同一真实实体”的编号集合。每一行输入代表某个引擎得到的一组编号（集合），行内的编号可能有重复。若两组集合存在至少一个公共编号，则它们应当被视作同一簇，需合并为一个更大的集合。请你将所有集合按上述规则进行传递式合并与去重，并按指定顺序输出。

编号仅由数字字符构成（如“1”“23”“0005”），每行不超过100个编号，总不同编号数不超过100000，匹配系统行数 N 在 1 到 10000 之间。

排序规则
- 行内排序：将一个合并后的集合中的编号按字典序（字符串比较）升序排列后输出为一行，编号之间用单个空格分隔。
- 行间排序：将所有行作为“编号有序序列”，按字典序（逐个编号从左到右比较，若一行是另一行的前缀，则较短者更小）升序排列后输出。

输入描述:

第1行：整数 N，表示有 N 行匹配结果。
接下来的 N 行：每行是若干个用空格分隔的数字字符串，表示该系统判定为“同一实体”的编号集合。行内可能出现重复编号。

输出描述:

输出 M 行（M ≤ N）。每一行是一组经传递式合并与去重后的编号序列，满足“行内字典序、行间字典序”的排序要求。

示例1

输入

输出

说明

解释如下（按“字符串字典序”进行排序）：

合并关系
- 第4行“7 7 8 9”和第6行“9 11”因共同包含“9”，属于同一簇，合并为集合{7,8,9,11}，并去重。
行内排序（字符串字典序）
- 合并后的集合按字符串排序为“11 7 8 9”（因为“11”作为字符串小于“7”“8”“9”）。
- 其余行分别为：“10 20”“30 40”“500”“1”。
行间排序（按整行序列的字典序进行比较）
- 比较每行的第一个编号，得到整体顺序：
  1
  10 20
  11 7 8 9
  30 40
  500