Union-Find是什么
详情参考：
Union-Find其实是一种解决图的连通性问题的算法。或者说解决某张图里连通分量的问题。比如说最简单的Number of Islands，就是查找图里有多少个连通分量。
其实并查集的问题并不多，而且绝大多数并查集用DFS也都能够解决，union-find主要是一种思想，某些情况下会有不错的效果。
Union-Find基础思路
思想推导
基本操作Union与Find
这里推导只是简单的文字描述，作图的话时间不太充沛，以后有机会再补，觉得看不懂可以参考第一节里的参考资料，里面有很详细的分析。
首先，我们假设有n个独立的节点，我们定义每个节点i存在它的parent[i]，初始化为自己本身。
然后我们定义两种操作，Union和Find。
- Union的过程就是将两个节点连接起来的过程，如果我们Union(a, b)，那么我们就将a的parent节点设置为b。
- Find的过程就是找到某节点的root节点，root节点就是一级一级向上找，直到找到某个节点的parent节点是本身，该节点就是root节点。
优化
Path Regression（Find优化）
在find的时候，每次找到root节点时，可以将路径上所有节点的parent全部都指向root节点，这样的话可以保证树的高度不会很高，每次查询都可降低后续查询的复杂度。
Merge Optimization（Union优化）
在Union的时候，我们希望把比较小的树连接到比较大的树上，这样整棵树的高度不会更高。因此我们需要一个size，来记录每棵树的大小。
基础代码
class UF {
int[] parent; // 每个连通分量的父节点
int[] size; // 每个连通分量的大小
int count; // 当前有多少个连通分量
public UF (int n) {
parent = new int[n];
size = new int[n];
count = n;
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
// 合并的时候把size小的merge到高的上
public void union(int a, int b) {
int rootA = findRoot(a);
int rootB = findRoot(b);
if (rootA == rootB) {
return;
}
if (size[rootA] >= size[rootB]) {
parent[rootB] = rootA;
size[rootA] += size[rootB];
} else {
parent[rootA] = rootB;
size[rootB] += size[rootA];
}
count--;
}
// 找到根节点这种写法是将树的高度压缩为3以内
// private int findRoot(int x) {
// while (x != parent[x]) {
// parent[x] = parent[parent[x]];
// x = parent[x];
// }
// return x;
// }
//这种写法是把树的高度压缩成2，一个根带多个孩子
public int findRoot(int x) {
if (x != parent[x]) {
parent[x] = findRoot(parent[x]);
}
return parent[x];
}
}拓展：有向图的Union-Find
经典题目就是：LeetCode 685. Redundant Connection II