#P2017. 分组
分组
Problem Description
kuro在自学的时候,开始沉迷一款叫做maimai的音游。
在音游中,玩家需要按照某种时间点击打音符,根据击打时间和标准击打时间的差距进行评判玩家分数。
在游玩中,有经验的玩家一般会将某些需要击打的音符看成是一组音符,一起处理,以降低难度。
kuro想尝试这种方案。具体的说,一共有个音符,每次会给出个音符,kuro认定它们应该属于同一组。
两个音符,当且仅当符合以下两种情况时属于同一组(具体例子请阅读样例和样例解释)
1.在kuro的某一次认定中被认为属于同一组音符
2.因为第一种或此前因该种情况被认为属于同一组音符,也因为第一种或此前因该种情况被认为属于同一组音符
现在给出音符的总数,以及给出组kuro认为应该属于同一组的音符,kuro感到很好奇,一共有多少组音符呢?
注意:没有被认为和其他音符属于同一组的音符应该也属于某一组,且该组的成员只有其自己。
Input Format
每个测试点的第一行包含两个整数 和 (, ),分别表示音符的总数和给出的分组数量。
接下来的 行,每行的第一个整数表示该组的音符数量,若k不为0,接下来的 个整数为音符的编号。
保证每个测试点的所有的总和不超过
注意:可能会出现在前面被认为是同一组的音符再次被认为属于同一组(详情请看样例)
Output Format
输出一个整数,表示最终的音符组数。
Sample
输入 #1
6 5
3 1 2 5
2 4 3
2 1 5
2 6 6
2 1 1
输出 #1
3
样例解释
- 输入的第二行表示音符 1, 2, 5 属于同一组。
- 第三行表示音符 3, 4 属于另一组。
- 第四行此前音符 5 已经与音符 1, 2 在同一组中,实际上没有任何影响
- 第五,六行并没有进行任何合并操作,实际上没有任何影响
- 因此最终分为 3 组:{1, 2, 5} , {4, 3} 和 {6}。
输入 #2
6 0
输出 #2
6
样例解释
- 并没有进行任何合并操作。
输入 #3
6 3
3 1 2 3
2 4 5
3 1 5 2
输出 #3
2
样例解释
- 输入的第二行表示音符 1, 2, 3 属于同一组。
- 第三行表示音符 4, 5 属于另一组。
- 第四行合并了前两行产生的两组。
- 因此最终分为 2 组:{1, 2, 3, 4, 5} 和 {6}。
Hint
p.s.这道题还有medium version和hard version,期待能在未来让这两个版本问世,敬请关注2025重邮校赛
相关
在下列比赛中: