🐷大肚肚
CF-82B3

集合

2.0s💾 256MB

📋 题目描述

胖球肚拥有 nn 个互不相交的非空集合,这些集合两两之间没有公共元素,本题把这 nn 个集合称为原始集合 。现在胖球肚在 n(n1)2\frac{n\cdot (n-1)}{2} 张卡片上记录了这些集合的两两并集的信息,每张卡片上记录两个原始集合的并集,没有两张卡片上记录的信息相同。现在给定了所有卡片上的信息, 你的任务是根据这些卡片上的信息恢复原始的集合信息。

📥 输入格式

第一行仅有一个整数 nn ( 2n2002\le n \le 200 ) 表示原始集合的个数,接下来的 n(n1)2\frac{n\cdot (n-1)}{2} 行,一次给出每张卡片上的信息,即每行给出一个集合,也就是两个原始集合的并集,每个集合以整数 kk ( 2k2002\le k \le 200 ) 开头,表示该集合元素的个数,之后跟着 kk 个整数 a1,a2,...,aka_1,a_2,...,a_k ( 1ai2001\le a_i \le 200 ) ,一行中的多个集合元素,两两之间用空格分隔。数据保证 nn 个原始集合两两之间均没有公共元素。

📤 输出格式

共有 nn 行,给出原始的 nn 个集合,每行描述一个集合,对于每个集合,都以一个整数 mm 口头,表示该集合的元素个数,紧随其后的 mm 个数表示该集合中的元素。同一行的多个数,两两之间用一个空格分隔。

📝 样例 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

📚 来源

💡 题目讲解

1

理解题意

nn 个互不相交的"原始集合"(两两无公共元素)。胖球肚记录了所有 n(n1)2\frac{n(n-1)}{2}两两并集卡片——每张卡片 = 两个不同原始集合的并集。根据所有卡片,恢复原始集合。

关键观察:属于同一个原始集合的元素,出现在完全相同的卡片里

为什么?假设元素 x 来自集合 A。A 与另外 n-1 个集合各有一张并集卡片,x 正好出现在这 n-1 张上。A 中的另一个元素 y 也出现在这 n-1 张上。所以 x 和 y 的"出镜清单"一模一样。

1 / 4