#P0832. 聚合离散
聚合离散
题目描述
勾心斗角
某星光高中近期发现许多学生之间建立了一个又一个的小团体,现在老师对这个问题开始着手解决了。
班级中有名同学,每位同学都有一个仰慕的同学,每位同学仰慕的同学互不相同,同学可以仰慕自己,且:
- 传递性:如果仰慕,仰慕,那么也仰慕。
- 非对称性:如果仰慕,不一定仰慕。
根据仰慕关系,学生之间形成以下类型的团体:
-
互慕团体:一个人数至少为的学生集合 ,其中对于任意两名不同的学生 , 仰慕 且 仰慕 (即相互仰慕);或者中只有一名学生,且他自己仰慕自己。
-
单慕团体:一个人数至少为的学生集合 ,其中对于任意两名不同的学生 , 仰慕 或 仰慕 (即有单向仰慕关系),但并非所有人都相互仰慕;或者 中只有一名学生,且他不仰慕自己。
-
孤立团体:只有一名学生的单慕团体。
-
非孤立单慕团体:不是孤立团体的单慕团体。
老师为了防止小团体影响学生们的成绩,开始了拆散计划:老师将点名约谈位同学,如果同学被约谈,对所有曾经“仰慕”的同学都将变为“讨厌”关系(仰慕 讨厌)。进而,将被所在团体孤立出去,并不再仰慕任何人(包括自己),原先包含的”互慕团体“中的同学将不再相互仰慕而变成“单慕团体”,原先包含的“单慕团体”也可能被分裂成多个“单慕团体”,同时自己一个人变成一个“孤立团体”。
经过约谈,班级里的团体被拆的七零八散,同学们察觉到了老师的意图,团结了起来。
同学们相互沟通,所有“非孤立单慕团体”将两两配对,每两个”非孤立单慕团体“将相互仰慕合并成一个新的”互慕团体“。如果有落单的”非孤立单慕团体“,那他将变成孤立收容所,将所有的”孤立团体“纳入其中,组建成一个新的”互慕团体“。
如果没有孤立收容所,每个”孤立团体“都将自立自爱,成为一个只有自己一个人的”互慕团体“。
请问最后,班级中会剩多少个互慕团体呢?
输入格式
本题包含多组测试数据。
第一行为一个整数,表示测试数据组数。
对于每组测试数据,第一行为一个整数,班级中的人数。
第二行包含个整数,其中表示同学仰慕的同学编号。保证如果,则。
第三行为一个整数,老师带走约谈的同学数。
第四行包含个整数,被老师带走约谈的位同学的编号。保证如果,则。
对于所有测试数据,保证。
输出格式
对于每组测试数据,输出一行一个整数,表示班级中最后剩下的互慕团体数。
样例
3
7
2 1 5 3 4 7 6
2
2 4
10
5 3 9 8 7 6 1 10 2 4
4
3 1 5 8
9
2 3 4 5 6 7 8 9 1
3
1 3 5
2
7
1
提示
对于第一组测试数据,老师约谈后的团体情况为:
- 互慕团体:
- 非孤立单慕团体:
- 孤立团体:
原来有 个互慕团体 ,落单的非孤立单慕团体变为孤立收容所,和所有的孤立团体共同组成 个互慕团体。
对于第二组测试数据,老师约谈后的团体情况为:
- 互慕团体:
- 非孤立单慕团体:
- 孤立团体:
原来有 个互慕团体,两个非孤立单慕团体组成 个互慕团体后,没有落单的非孤立单慕团体。个孤立团体变成 个互慕团体。