CF-82B3
集合
⏱ 2.0s💾 256MB
📋 题目描述
胖球肚拥有 个互不相交的非空集合,这些集合两两之间没有公共元素,本题把这 个集合称为原始集合 。现在胖球肚在 张卡片上记录了这些集合的两两并集的信息,每张卡片上记录两个原始集合的并集,没有两张卡片上记录的信息相同。现在给定了所有卡片上的信息, 你的任务是根据这些卡片上的信息恢复原始的集合信息。
📥 输入格式
第一行仅有一个整数 ( ) 表示原始集合的个数,接下来的 行,一次给出每张卡片上的信息,即每行给出一个集合,也就是两个原始集合的并集,每个集合以整数 ( ) 开头,表示该集合元素的个数,之后跟着 个整数 ( ) ,一行中的多个集合元素,两两之间用空格分隔。数据保证 个原始集合两两之间均没有公共元素。
📤 输出格式
共有 行,给出原始的 个集合,每行描述一个集合,对于每个集合,都以一个整数 口头,表示该集合的元素个数,紧随其后的 个数表示该集合中的元素。同一行的多个数,两两之间用一个空格分隔。
📝 样例 1
输入
4 3 2 7 4 3 1 7 3 3 5 4 2 3 1 3 5 4 3 1 2 4 2 5 7
输出
1 7 2 2 4 2 1 3 1 5
📝 样例 2
输入
4 5 6 7 8 9 100 4 7 8 9 1 4 7 8 9 2 3 1 6 100 3 2 6 100 2 1 2
输出
3 7 8 9 2 6 100 1 1 1 2
📝 样例 3
输入
3 2 1 2 2 1 3 2 2 3
输出
1 1 1 2 1 3
📚 来源
Problem:CF-82B
💡 题目讲解
1
理解题意
有 个互不相交的"原始集合"(两两无公共元素)。胖球肚记录了所有 张两两并集卡片——每张卡片 = 两个不同原始集合的并集。根据所有卡片,恢复原始集合。
关键观察:属于同一个原始集合的元素,出现在完全相同的卡片里。
为什么?假设元素 x 来自集合 A。A 与另外 n-1 个集合各有一张并集卡片,x 正好出现在这 n-1 张上。A 中的另一个元素 y 也出现在这 n-1 张上。所以 x 和 y 的"出镜清单"一模一样。
1 / 4