摘要：
1，并查集的介绍
2，并查集的查找
3，并查集的合并
1，并查集的介绍
并查集(Disjoint-set data structure，不交集数据结构)是用于处理一些不交集的合并以及查询问题，它是非常重要的一种数据结构，在信奥赛，蓝桥杯等比赛中用到的非常多，主要用于图论算法中。
在并查集中，刚开始的时候，每个元素都是一个单独的连通分量，还没有发生合并，如下图所示：
Java 代码：
public class UnionFind {
private int[] parent; // 记录每个元素所在的连通分量。
private int count;// 连通分量个数。
// 构造函数。
public UnionFind(int n) {
count = n;// 连通分量的个数
parent = new int[n];
// 初始化不同值，每个元素都是一个单独的连通分量
for (int i = 0; i < n; i++)
parent[i] = i;
}
}
C++ 代码
class UnionFind {
private :
vector<int> parent;// 记录每个元素所在的连通分量。
int count;// 连通分量个数。
// 构造函数。
public :
UnionFind(int n) : count(n), parent(n) {
// 初始化不同值，每个元素都是一个单独的连通分量
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
};
这里说明一下数组parent的含义，假如每个连通分量都有编号，那么 parent[5]=3 就表示元素 5 在编号为 3 的连通分量中。
2，并查集的查找
并查集我们可以把它看作是一个森林，每个连通分量可以把它看作是一棵树，其中树中根节点的值就是连通分量的编号，其它非根节点的值都不等于它所在的连通分量的编号。子节点的parent[i]等于父节点的值，根节点的parent[i]等于它自己。
