并查集
在计算机科学中，并查集是一种树型的数据结构，其保持着用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个操作用于此数据结构：
Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。引用自wikipedia并查集
写并查集算法，主要是对“集合”这种数学上的数据结构进行操作。操作有：
- 查询操作；
- 合并操作。
这两种操作操作的对象是一些集合。但是计算机中难以将“集合”这种数据结构直接表达，我们可以维护许多棵树来当作集合（即并查集森林）。使用树这种数据结构可以让并查集操作复杂度达到最优，水平有限，不做证明。当节点在同一棵树上，认为节点在一个集合内。我们把每棵树的祖先（根）节点作为这个集合的代表。
查询任意两个节点是否属于同一个集合时，我们只需要找到这两个节点的祖先，若相同，则这两个节点在同一棵树上，即在同一个集合内。
我们需要做两个集合的合并操作时，我们只需要找到这两个集合的代表，及这两个集合对应的树的根，将两个根合并即可。合并操作即将其中任意一棵树的根指向另一个根，如何选取哪棵树作为最终的根属于并查集操作的优化。
在做查询或合并操作时，我们需要对并查集进行初始化操作，初始化操作只需要将每个节点的根指向自己：
初始化：
/*CPP code*/
void initialize()
{
for (int i = 1; i <= n; i++)
{
parent[i] = i;
}
}查询操作，及找到当前节点的祖先，可以递归实现：
/*CPP code*/
int find_parent(int i)
{
if (parent[i] != i)
return find_parent(parent[i]);
return i;
}合并操作，合并a所在的集合与b所在的集合，找到a的祖先与b的祖先，将其合并（将a的根指向b的根）：
/*CPP code*/
void union_parent(int a, int b)
{
parent[find_parent(a)] = find_parent(b);
}到此，最基本的并查集就结束了。但是！重要的是但是。
同学们一定不会满足于搞懂“最基本”的并查集算法，作为一个程序员应该有的自我修养，应该明白大公司炒鸡bt，任何一点可以优化的细节都不会放过。
并查集操作进行时也有许多可以优化之处，我们从简单的说起。
优化一
减小树的深度
前面说到，我们在构建许多棵树作为并查集森林时，我们仅仅需要知道任意两个节点是否属于同一棵树，而不会在意某一棵树的结构形态。并且我们在查找一个节点的祖先时，我们希望这棵树的深度越小越好，这样我们递归（或者循环）的深度（次数）就会大大减小。
因此，我们在做并查集操作时会想此操作能否尽可能的减小树的深度，最容易想到的就是查找祖先节点的操作，在找一个节点的祖先节点过程中，如果此节点不是祖先节点，那么就把这个节点的根指向祖先节点，最终将此祖先节点返回：
/*CPP code*/
int find_parent(int i)
{
if (parent[i] != i)
parent[i] = find_parent(parent[i]);
return parent[i];
}优化二
按秩合并
我们使用一棵树来当作集合，尽管我们希望树的深度很小，但是在操作过程中不可避免的会使树的深度增加，这无疑会影响操作速度。但是我们可以尽量平衡每棵树的结构，这棵树“越稳重”，查迅速的相对更快。
所以我们总是希望在合并操作时将一棵更小的树合并到更大的树，这样将不会增加树的深度。但是由于‘优化一’中的路径压缩，一棵树的深的并总是代表这棵树的规模。因此我们引入一个新术语“秩”。
我们在初始化时将每个集合的秩设为0，每次两个秩相同的树合并时，合并后的树的秩加1，如果将秩比较小的树合并到秩比较大的树上，秩不会改变。以下是采用“按秩合并”方法后的初始化操作及合并操作代码：
初始化：
/*CPP code*/
void initialize()
{
for (int i = 1; i <= n; i++)
{
parent[i] = i;
rank_[i] = 0;
}
}合并操作：
/*CPP code*/
void union_parent(int a, int b)
{
int a_root = find_parent(a);
int b_root = find_parent(b);
if (a_root == b_root)
return;
if (rank_[a_root] < rank_[b_root])
parent[a_root] = b_root;
else if (rank_[a_root] > rank_[b_root])
parent[b_root] = a_root;
else
parent[a_root] = b_root;
rank_[a_root]++;
}！！！！！！！！！！！实际上，优化后OJ上提交使用内存竟然多了4KB，时间却一点也没有减少！！！！！！！！！！！！！！！！！！！！！！！！
还真是见鬼了！！！！！！
例题有：