POJ 1611 – The Suspects (并查集)

原题地址:《The Suspecst》

题目大意:某学校有N个学生,M个社团,每个学生可以属于多个社团。SARS流行,但是社团活动频繁,一旦一个社团有一个人是SARS疑似,所有人都是SARS疑似。现在假定第0号学生是SARS疑似,求所有疑似病例。

这个就是典型的并查集问题……我挑了这个最水的问题实践了一下。和刚才哪篇并查集无异。数据弱所以连rank union都不用就能过。

思路是:每个社团读取后直接把他们union起来。最后将学生0的parent和其他N-1个学生比较(来判断他们是否属于一个集合),如果一样的,sum++。最后输出sum。

代码是有优化余地的:实际上,每次union的时候就能知道每个set有多少新元素。这样就不用最后再遍历依次n个学生的find_set了!

Leave a Reply

Your email address will not be published.