数据结构这书感觉和之前没读过一样……以前从来没发现树这章还讲了并查集……
若R是集合S上的一个等价关系，则由这个等价关系可以产生这个集合的唯一划分。
如何划分等价类
假设集合S有n个元素，m个形如(x, y)，的等价偶对(x, y都是集合S中的元素)。
(1)令S中每个元素各自形成一个只含单个成员的子集，记作S1, S2, ..., Sn。
(2)依次读入m个偶对，对每个读入的偶对(x, y)，判定x和y所属的集合，若他们还不属于同一集合，设x属于Si，y属于Sj，则合[......]
原题地址：《The Suspecst》
题目大意：某学校有N个学生，M个社团，每个学生可以属于多个社团。SARS流行，但是社团活动频繁，一旦一个社团有一个人是SARS疑似，所有人都是SARS疑似。现在假定第0号学生是SARS疑似，求所有疑似病例。
这个就是典型的并查集问题……我挑了这个最水的问题实践了一下。和刚才哪篇并查集无异。数据弱所以连rank union都不用就能过。
思路是：每个社团读取后直接把他们union起来。最后将学生0的parent和其他N-1个学生比较(来判断[......]
背景：如果我们需要将元素划分到若干不相交的子集中，使用并查集可以快速确定某两个元素是否位于同一个子集。
并查集是一种数据结构，除了Union-Find Set，又叫做Disjoint-Set。更确切的说，它主要包含了两种操作：Find和Union。具体信息可以见维基百科：《Disjoint-set data structure 》
并查集主要包含两个操作：
Find(x)：返回元素位于那个划分的子集合内。
Union(x, y)：将x, y两个集合中的元素合并为一个集合。[......]