vlambda博客
学习文章列表

并查集的定义

给定n个结点的集合，结点编号为1～n，再给定一个等价关系，由等价关系产生所有结点的一个划分，每个结点属于一个等价类，所有等价类是不相交的。

需要求一个结点所属的等价类，以及合并两个等价类。

并查集的实现

并查集就是一个森林。

每个等价类用一棵树表示，包含该等价类的所有结点，即结点子集，

每个子集通过一个代表来识别，代表即该子集中的某个结点，通常选择根做这个代表。

    问题描述：如果已经得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系就十分复杂。在这种情况下，就需要应用并查集。

    为了将问题简化，将得到一些亲戚关系的信息，如Marry和Tom是亲戚，Tom和Ben是亲戚，等等。从这些信息中，可以推出Marry和Ben是亲戚。

用有根树来表示集合，树中的每个结点包含集合的一个成员，每棵树表示一个集合。

多个集合形成一个森林，以每棵树的树根作为集合的代表，并且根结点的父结点指向其自身，树上的其他结点都用一个父指针表示它的附属关系。      

在并查集中，每个分离集合对应的一棵树，称为分离集合树。整个并查集也就是一棵分离集合森林。

4个集合{1，2，3，4}、{5，6，7}、{8，9}、{10}，分别以4、7、9和10表示对应集合的编号。

查找x

查找x所在的子集

合并过程

查找中的路径压缩

并查集的基本存储结构（实际上是森林的双亲存储结构）如下：

并查集的基本运算算法

时间复杂度为O(n)。

用迭代方式实现

HDU1232—畅通工程问题。

   问题描述：某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

   输入格式：测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N（N<1000< span="">）和道路数目M，随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。注意两个城市之间可以有多条道路相通，也就是说：

   3 3

   1 2

   1 2

   2 1

这种输入也是合法的。当N为0时，输入结束，该用例不被处理。

要使全省任何两个城镇间都实现交通，最少的道路是所有城镇之间都有一条路径，即全部城镇构成一棵树。

采用并查集求解，由输入构造并查集，每棵子树中的所有城镇是有路径的，求出其中子树的个数ans，那么最少还需要建设的道路数就是ans-1。