转自https://www.cnblogs.com/noKing/p/8018609.html
并查集是一种数据结构, 常用于描述集合,经常用于解决此类问题:某个元素是否属于某个集合,或者 某个元素 和 另一个元素是否同属于一个集合
数组里存的数字代表所属的集合。比如arr[4]==1;代表4是第一组。如果arr[7]==1,代表7也是第一组。既然 arr[4] == arr[7] == 1 ，那么说明4 和 7同属于一个集合，
/**基本并查集:
* 数组实现并查集，元素内数字代表集合号
*/
public class UnionFind {
/**
* 数组，表示并查集所有元素
*/
private int[] id;
/**
* 并查集的元素个数
*/
private int size;
/**
* 构造一个新的并查集
*
* @param size 初始大小
*/
public UnionFind(int size) {
//初始化个数
this.size = size;
//初始化数组，每个并查集都指向自己
id = new int[size];
for (int i = 0; i < size; i++) {
id[i] = i;
}
}
/**
* 查看元素所属于哪个集合
*
* @param element 要查看的元素
* @return element元素所在的集合
*/
private int find(int element) {
return id[element];
}
/**
* 判断两个元素是否同属于一个集合
*
* @param firstElement 第一个元素
* @param secondElement 第二个元素
* @return <code>boolean</code> 如果是则返回true。
*/
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
/**
* 合并两个元素所在的集合，也就是连接两个元素
*
* @param firstElement 第一个元素
* @param secondElement 第二个元素
*/
public void unionElements(int firstElement, int secondElement) {
//找出firstElement所在的集合
int firstUnion = find(firstElement);
//找出secondElement所在的集合
int secondUnion = find(secondElement);
//如果这两个不是同一个集合，那么合并。
if (firstUnion != secondUnion) {
//遍历数组，使原来的firstUnion、secondUnion合并为secondUnion
for (int i = 0; i < this.size; i++) {
if (id[i] == firstUnion) {
id[i] = secondUnion;
}
}
}
}
并查集：快速Union，慢Find
Find这样的合并操作太低效了，合并一次就O(n)。所以采用快速Union方式。
思路:原先的数组中存的是小组号(或者队长的编号)，而现在数组中存的是自己的‘大哥’的编号。(应该说是父亲结点，和父亲数组，但为了更形象，还是叫‘大哥’更好理解)。
每个元素都可以去认一个大哥去保护自己，避免被欺负。只能认一个大哥...不能认多个
/**
* 数组模拟树，实现并查集。数组内的元素表示父亲的下角表，相当于指针。
*/
public class UnionFind {
private int[] parent;
private int size;
public UnionFind(int size) {//自己指向自己
this.size = size;
parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
public int find(int element) {
while (element != parent[element]) {
element = parent[element];
}
return element;
}
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
public void unionElements(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
if (firstRoot == secondRoot) {
return;
}
parent[firstRoot] = secondRoot;
}
并查集：快速union，快速find，基于重量
思路和例子:其实上面讲的union函数，没有采取合理的手段去进行合并。每次都以secondElement为主，每次合并两个集合都让secondElement的根来继续充当合并之后的根。这样很可能达到线性的链表的状态。
那合并的时候怎么处理更好呢？
比如：有下面两个集合。其中 2 和 6 是两个集合的根。下面要让这两个集合合并，但是，合并之后只能有一个老大啊，到底谁来当呢？
在基于重量的union里，谁的人手多，就由谁来当合并之后的大哥。
2元素有4个手下，再算上自己，那就是5个人。
6元素有2个手下，再算上自己，那就是3个人。
很明显是2元素的人手多，所以2来充当合并之后的根节点。
public class UnionFind {
private int[] parent;
private int[] weight;
private int size;
public UnionFind(int size) {
this.parent = new int[size];
this.weight = new int[size];
this.size = size;
for (int i = 0; i < size; i++) {
this.parent[i] = i;
this.weight[i] = 1;
}
}
public int find(int element) {
while (element != parent[element]) {
element = parent[element];
}
return element;
}
public boolean isConnected(int firstElement, int secondElement) {
return find(firstElement) == find(secondElement);
}
public void unionElements(int firstElement, int secondElement) {
int firstRoot = find(firstElement);
int secondRoot = find(secondElement);
//如果已经属于同一个集合了，就不用再合并了。
if (firstRoot == secondRoot) {
return;
}
if (weight[firstRoot] > weight[secondRoot]) {
parent[secondRoot] = firstRoot;
weight[firstRoot] += weight[secondRoot];
} else {//weight[firstRoot] <= weight[secondRoot]
parent[firstRoot] = secondRoot;
weight[secondRoot] += weight[firstRoot];
}
}
