数据结构(5.5_3)——并查集的进一步优化

Find操作的优化(压缩路径)

压缩路径——Find操作，先找到根节点，再将查找路径上所有结点都挂到根结点下

代码：

//Find "查"操作优化，先找到根节点，再进行"路径压缩"
int Find(int S[], int x) {int root = x;while (S[root] >= 0)root = S[root]; //循环寻找x的根while (x != root) {//压缩路径int t = S[x]; //t指向x的父节点S[x] = root;//x直接挂到根节点下x = t;}return root;//返回根节点编号 
}

 

并查集的优化