在一些有n个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在规定的运行时间（1～3秒）内计算出试题需要的结果，只能用并查集来描述。
并查集（disjoint
set），即“不相交集合”，是一种树型的数据结构，用于处理一些不相交集合（disjoint
sets）的合并及查询问题。常常在使用中以森林来表示。集就是让每个元素构成一个单元素的集合，也就是按一定顺序将属于同一组的元素所在的集合合并。
将编号分别为1…n的n个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合。
常见两种操作：
合并两个集合
查找某元素属于哪个集合
用编号最小的元素标记所在集合；定义一个数组 set[1..n] ，其中set[i] 表示元素i 所在的集合；
查找 Θ(1)
合并 Θ(n)
对于“合并操作”，必须搜索全部元素！有没有可以改进的地方呢？
每个集合用一棵“有根树”表示，定义数组 set[1..n]
set[i] = i , 则i表示本集合，并是集合对应树的根
set[i] = j, j<>i, 则 j 是 i 的父节点.
查找 最坏情况Θ(n)
合并 Θ(1)
性能有无本质的改进？如何避免最坏情况呢？
方法：将深度小的树合并到深度大的树
实现：假设两棵树的深度分别为h1和h2, 则合并后的树的高度h是:
max(h1,h2), if h1<>h2.
h1+1, if h1=h2.
效果：任意顺序的合并操作以后，包含k个节点的树的最大高度不超过lgk
优化后算法及效率：
查找 Θ(n)
思想：每次查找的时候，如果路径较长，则修改信息，以便下次查找的时候速度更快
步骤:
第一步，找到根结点
第二步，修改查找路径上的所有节点，将它们都指向根结点
带路径压缩的查找算法：
路径压缩示意图:
<a href="http://acm.hdu.edu.cn/showproblem.php?pid=1232" target="_blank">（hdoj1232）畅通工程</a>
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
典型的并查集题目
算法：
判断图是否连通且无回路
如果待连接的两点如果祖先节点相同，那么就构成回路，不符合
如果不构成回路，但是有多个根节点，也不符合
题目大意：
给你一些操作，p后边输入四个值，分别代表一条线段的起点、终点坐标，
当输入q时，后边输入一个整形值k，输出第k条线段所在的集合中包含的线段的个数
思路：并查集+计算几何线段相交
当输入p时，判断后边输入的线段的起点和终点时，判断跟之前的线段有没有相交，如果有相交，就merge（）合并，
如果输入的是q时，就打印出当前线段所在集合的个数