Tag Archives: SARS

POJ 1611 - The Suspects (并查集)

原题地址:《The Suspecst》

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

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

思路是:每个社团读取后直接把他们union起来。最后将学生0的parent和其他N-1个学生比较(来判断[......]

继续阅读