并查集是一种树形数据结构，用来处理一些不想交集合的合并和查询操作。
- 并（Union），代表合并,将两个子集合并成一个集合。
- 查（Find），代表查找，确定元素属于哪一个子集。
- 集（Set），代表它的基本功能是合并集合中的元素，查找集合中的元素
并查集的数据结构和树类似，不过和树不同的是，树的每个节点会记录它的子节点，而在并查集里，它的节点会记录它的父节点。
对于一组数据来说，并查集主要支持两个动作
- union(x, y)
- find(x)
用来回答一个问题 - isConnected(x, y)
我们把一组数据用数据来表示，数组的索引代表该元素，索引对应的值来代表该元素所对应的集合编号。
所以，我们要实现一个并查集的类，基础数据为
- int[] parents;
构造函数为
public UnionFind(int n) {
this.parents = new int[n];
for (int i = 0; i < n; i++) {
parents[i] = i;
}
}
这样构造完成之后，每个元素都位于它自己所在的集合里。
此时的find函数为
public int find(int x) {
assert (x<0 || x >= parents.length);
return parents[x];
}
而isConnected函数则为
public boolean isConnected(int x, int y) {
return find[x] == find[y];
}
对于union函数，两个集合如果想合并成一个集合，那么他们集合编号应该相同，所以我们将任意一方的集合编号修改为另一方的集合编号就可以了。
public void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) {
return;
} else {
int len = parents.length;
for (int i = 0; i < len; i++) {
if (parents[i] == yRoot) {
parents[i] = xRoot;
}
}
}
}
这么看起来，每次合并都要遍历一边数组，效率非常低，所以我们调整一下，每个元素的索引还是代表它自身，但是这个元素代表着它的父节点，x = parents[i] 就表示 x是i的父节点，而父节点是自身的节点就是根节点。查询操作调整为查询其根节点，合并操作则调整为把一个集合的根节点指向另一个集合的根节点作为父节点。
上图对应的就是下边的集合合集。
这时，find函数为
public int find(int x) {
assert (x<0 || x >= parents.length);
while(x != parents[x]) {
x = parents[x];
}
return parents[x];
}
相应的 union也需要调整一下
public void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) {
return;
} else {
parents[yRoot] = xRoot;
}
}
而检查两个数是否在一个集合内的函数不需要调整。
基于Size或者Rank优化
这里考虑一下特殊情况。
如果已有的两个集合如下图所示
按照之前的写法，将两个集合合并起来的时候，是将4这个节点指向1这个节点，看起来没什么问题，如果换一种情况
这样，合并完成之后就变成了 0 - 1 - 2 - 3，如果还有更多的话，这条链就会一直增长下去，这样在我们执行find函数查找链末端元素的时候，它要从底部往上查找很多次才能查到。
所以，我们找到了一种优化的方法。
引入了一个size的数组，用来记录这个集合里现在有多少元素，然后在合并的时候，我们借用Size数组来查询需要合并的两个集合当中哪一个集合中的元素个数比较少，就可以把Size数小的集合并入Size数大的集合当中去。
在基础数据中增加一个数组
- int[] size;
在初始化的时候，将size的默认值设定成1
public UnionFind(int n) {
this.parents = new int[n];
for (int i = 0; i < n; i++) {
parents[i] = i;
size[i] = 1;
}
}
然后在合并的时候，判断并修改相应的size值
public void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) {
return;
} else {
if (size[xRoot] > size[yRoot]) {
parents[yRoot] = xRoot;
size[xRoot] += size[yRoot];
} else {
parents[xRoot] = yRoot;
size[yRoot] += size[xRoot];
}
}
}
当然，这种优化有时候也会满足不了我们的需求，比如，碰到以下这种情况
这种时候，如果按照size来合并的话，结果如下
这个时候，我们如果使用find函数查询9的根的话，我们需要查询4次，可是，如果我们反过来，让前面的集合合并到后边的集合上
我们查询最下边的节点9，只需要查询3次，所以我们又有了一种优化思路，根据“树高”来优化，我们不再使用size数组了，而是增加一个rank数组来保存集合的高度。这时候，和size不同的是，我们不需要在每次合并的时候都要调整数组数据，因为矮一点的树向高一点的树合并的时候，高一点的树的高度并没有改变，当且仅当两个树高度一样的时候，我们才需要调整一颗树的高度，让另一颗树合并过来。
新增数组
- int[] rank;
我们初始化的时候，
public UnionFind(int n) {
this.parents = new int[n];
for (int i = 0; i < n; i++) {
parents[i] = i;
rank[i] = 1;
}
}
合并的函数也要进行调整
public void union(int x, int y) {
int xRoot = find(x);
int yRoot = find(y);
if (xRoot == yRoot) {
return;
} else {
if (rank[xRoot] > rank[yRoot]) {
parents[yRoot] = xRoot;
} else if (rank[yRoot] > rank[xRoot]) {
parents[xRoot] = yRoot;
} else {
parents[xRoot] = yRoot;
rank[yRoot]++;
}
}
}
如果我们通过大量测试的话，就会发现，基于Rank优化的时间会比基于Size优化的时间稍微长一点，这是因为前者多一层判断的缘故，但是却排除了一些极端情况，综合来看，还是基于Rank优化更好一点。