路径压缩、、

参考  路径压缩 - 云+社区 - 腾讯云

并查集中的find函数，可以用于查找某个节点的父亲节点，某些情况下，我们为了加快查找的速度，就要用到路径压缩的写法。

int find(int x)
{
int tmp,son;
son=x;
while(x!=pra[x])
x=pra[x];
while(son!=x)
{
tmp=pra[son];
pra[son]=x;
son=tmp;
}
return x;
}

我们一开始找到了x的父亲节点，之后，我们随着（X--->X的祖先）这条路，一直把这条路上的所有节点的父节点都标记为祖先节点。从而加快了查找的速度。

################################################################

有关并查集join函数的新认识：

1.如果不考虑树的整体结构，

void join(int b1,int b2)//两颗树的合并操作
{
int x=find(b1);//找到树b1的根节点
int y=find(b2);//找到树b2的根节点
if(x!=y)//如果两棵树不同根
pra[y]=x;//链接两棵树
}

2.需要考虑到树的整体结构：

void join(int b1,int b2)//两颗树的合并操作
{
int x=find(b1);//找到树b1的根节点
int y=find(b2);//找到树b2的根节点
if(x!=y)//如果两棵树不同根
pra[b2]=b1;//链接两棵树
}

其他东西：

1.FIND函数能查找子节点的祖先节点

2.采用了路径压缩的FIND函数、JOIN函数可以修改子节点的父亲节点。

######################################################

路径压缩的使用前提是不考虑树的整体结构，也就是说FIND函数必须采用第一种写法。