1、并查集Union Find
并查集，一种树形的数据结构，处理不相交的两个集合的合并与查询问题。
引用上面文章的经典解释并查集：
- 一个集合就像一个江湖门派，他们有一个教主（代表元），集合中每个元素只需要记住自己的上级，而不是教主
- find即查询某个元素的代表元（教主）
- union即把两个门派（集合），合并成一个，认一个教主
例子：
查find(x)
有个数组array，长度为10，若array[1] = 6，说明1号元素的上级是6号元素。array[6] = 6，说明6号元素的上级是6号元素，即6号是教主。并查集的查：find(x)，即找x元素的教主
public int find(int x ) {
// 如果x位置的值，等于x，说明x就是教主
if (x == array[x]) {
return array[x];
}
// 如果不是，查x位置的值的上级
return find(array[x]);
}
也可不用递归：
public int find(int x ) {
while(x != array[x]) {
// 查x位置的元素自己的上级
x = array[x];
}
return x;
}
并union(x,y)
两个集合合并，或者说两个门派合并，看似改动很大，其实只要让一个门派的教主给另一个门派的教主当上级即可。因为只关注两个集合的连通性。
// 传入两个门派的元素
public void union(int x, int y) {
//查教主
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
// 让Y门派的教主当X门派教主的上级
array[rootX] = rootY;
}
}
如下树形，
对应的数组：数组索引代表元素，数组的值，代表这个位置的元素的上级
合并后，比如让第一个集合的教主做合并后新集合的教主：5号的上级不再是自己，变成了1
2、并查集find的优化：路径压缩 Quick find
用开头引用文章的形象例子，现在要做的就是，防止树形结构过于深，导致查询效率变低，将结果压缩成，只要查一次，就能知道教主是谁：
总之一句话，防止树太高，期待右边，而不是左边
想实现这个效果，可以：查询到x元素的根节点（教主）后，直接将x元素的上级改成根节点。
public int QuickFind(int x ) {
// 如果x位置的值，等于x，说明x就是教主
if (x == array[x]) {
return array[x];
}
// 如果不是，查x位置的值的上级，等递归回退的时候，把x的上级改成根节点
return array[x] = find(array[x]);
}
也就是说，第一次find元素x，是没有压缩路径的，第二次才是优化后的效果
3、并查集union的优化：权重标记
和find优化属于同一思想，union两个集合时，防止树过高，比如合并：
如果这么连，树过高：
比较两棵树的高度，左边为2，右边为3，因此，高的树原地不动，继续做老大，低的树靠过去，union后的效果：
核心思想：
整体代码如下，带权重的union参考：
public class UnionFind {
const int N=1005 //指定并查集所能包含元素的个数（由题意决定）
int pre[N]; //存储每个结点的前驱结点的数组
int rank[N]; //树的高度，权重
void init(int n) { //初始化函数，对录入的 n个结点进行初始化
for(int i = 0; i < n; i++){
pre[i] = i; //每个结点的上级都是自己
rank[i] = 1; //每个结点构成的树的高度为 1
}
}
int find(int x) {
//查找结点 x的根结点
if (pre[x] == x) {
return x ; //递归出口：x的上级为 x本身，则 x为根结点
}
return find(pre[x]); //递归查找
}
int findQucik(int x) { //改进查找算法：完成路径压缩，将 x的上级直接变为根结点，那么树的高度就会大大降低
if (pre[x] == x) {
return x; //递归出口：x的上级为 x本身，即 x为根结点
}
return pre[x] = find(pre[x]); //此代码相当于先找到根结点 rootx，然后 pre[x]=rootx
}
bool isSame(int x, int y) { //判断两个结点是否连通
return find(x) == find(y); //判断两个结点的根结点（即代表元）是否相同
}
void union(int x,int y) {
int rootx = find(x); //寻找 x的代表元
int rooty = find(y); //寻找 y的代表元
if(rootx != rooty) { //如果 x和 y的代表元一致，说明他们共属同一集合，则不需要合并
if(rank[rootx] > rank[rooty]) { //如果 x的高度大于 y，则令 y的上级为 x
pre[rooty] = rootx;
} else if (rank[rootx] < rank[rooty]) {
pre[rootx] = rooty; //让 x的上级为 y
} else {
pre[rooty] = rootx;
rank[rootx] += 1; //如果 x的高度和 y的高度相同，则令 y的高度加1
}
}
}
}
