【笔记】数据结构与算法之并查集（UnionFind）
在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（Union-find Algorithm）定义了两个用于此数据结构的操作：Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union：将两个子集合并成同一个集合。
由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（Union-find Data Structure）或合并-查找集合（Merge-find Set）。
为了更加精确的定义这些方法，需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素，称为代表，以表示整个集合。接着，Find(x)Find(x)Find(x) 返回 xxx 所属集合的代表，而 Union 使用两个集合的代表作为参数。
直接上并查集代码，注释都在代码里面。
```
public class Main {
// size and compress
static class UnionFind{
// p is parentNode
int [] p ;
int [] size;
publicUnionFind(int n ){
//空着第一个元素
p = new int;
size = new int;
for (int i = 1;i<=n;i++){
p = i;
size=1;
}
}
public int getSize(){
return p.length;
}
public int find(int x){
if(x != p)
{
int t = find(p); //寻找根结点，找到后回溯
p = t; //路径压缩
//上面的部分可以这写成
// p = find(p);
}
return p;
}
public void union(int x , int y){
int rootX = find(x);
int rootY = find(y);
//如果两个节点的父亲节点是一样的话 就直接return 不处理
if (rootX==rootY){
return;
}
/**
* 把size 小的拼接到size大的树上，避免树的深度过高
*/
if (size<size) {
//rootX 的父亲节点就变成了 rootY 也就是挂接到rootY上了
p = rootY;
//roorY的大小就加等于rootX的大小了
size +=size;
}else {
p = rootX;
size+=size;
}
}
}
}
``` @alittlebear 今天不学习 明天变垃圾{:301_976:} 感谢分享，但是更喜欢c++刷题:lol 码上 发表于 2020-11-30 23:20
感谢分享，但是更喜欢c++刷题
哈哈哈，上学的时候c++没学好，哎，一大遗憾
页:
[1]