一、概念
并查集是一种树型的数据结构，用于处理一些不交集的合并及查询问题。
联合-查找算法定义了两个用于此数据结构的操作。
- Find:确定元素属于哪一个子集，可以用来确定两个元素是否属于同一个子集。
- Union:将两个子集合并成同一个集合
由于支持这两种操作，一个不相交集常被称为联合-查找数据结构或者合并-查找集合。
Find(x)：确定x属于哪个子集合
Union(x)：将子集合并为一个集合
主要作用：找出某个元素属于哪个子集合，将属于同一个子集合的元素合并起来
二、样例：
1、冗余连接
在本问题中, 树指的是一个连通且无环的无向图。
输入一个图，该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间，这条附加的边不属于树中已存在的边。
结果图是一个以边组成的二维数组。每一个边的元素是一对[u, v] ，满足 u < v，表示连接顶点u 和v的无向图的边。
返回一条可以删去的边，使得结果图是一个有着N个节点的树。如果有多个答案，则返回二维数组中最后出现的边。答案边 [u, v] 应满足相同的格式 u < v。
【解答】可运用并查集中合并不同子集的元素，若已在同一集合中，便不再进行合并，若存在，则说明已找到冗余边
①构建并查集类
class DSU{
int[] root;
int[] size;
public DSU(int n){
root = new int[n];
size = new int[n];
for(int i = 0;i<n;i++){
root[i] = i;
}
}
public int find(int x){
if(root[x]!=x){root[x] = find(root[x]);}
return root[x];
}
public boolean union(int x, int y){
int rootX = find(x);
int rootY = find(y);
if(rootX==rootY){return false;} //是同一个子集的，就不合并了，直接false掉
if(size[rootX]<size[rootY]){
root[rootX]=root[rootY];
size[rootY]++;
}else{
root[rootY]=root[rootX];
size[rootX]++;
}
return true;
}
}
②运用并查集解决实际问题
public int[] findRedundantConnection(int[][] edges){
int n = edges.length;
DSU dsu = new DSU(n+1);
for(int[] e:edges){
if(!dsu.union(e[0], e[1])){ //若属于同一子集，则直接将该边返回出
return e;
}
}
return new int[0];
}
该题目运用并查集可快速找到冗余的边。