并查集
文章目录
1. 概论
2. 并查集的现实意义
3. find( )函数的定义与实现
int find(int x) //查找x的教主 {
while(pre[x] != x) //如果x的上级不是自己（则说明找到的人不是教主） x = pre[x]; //x继续找他的上级，直到找到教主为止 return x; //教主驾到~~~ }
4. join( )函数的定义与实现
void join(int x,int y) //我想让虚竹和周芷若做朋友 {
int fx=find(x), fy=find(y); //虚竹的老大是玄慈，芷若MM的老大是灭绝 if(fx != fy) //玄慈和灭绝显然不是同一个人 pre[fx]=fy; //方丈只好委委屈屈地当了师太的手下啦 }
5. 路径压缩算法之一（优化find( )函数）
if(fx != fy) pre[fx]=fy; int find(int x) //查找结点 x的根结点 {
if(pre[x] == x) return x; //递归出口：x的上级为 x本身，即 x为根结点 return pre[x] = find(pre[x]); //此代码相当于先找到根结点 rootx，然后pre[x]=rootx } 该算法存在一个缺陷：只有当查找了某个节点的代表元（教主）后，才能对该查找路径上的各节点进行路径压缩。换言之，第一次执行查找操作的时候是实现没有压缩效果的，只有在之后才有效。
6. 路径压缩算法之二（加权标记法）
void union(int x,int y) {
x=find(x); //寻找 x的代表元 y=find(y); //寻找 y的代表元 if(x==y) return ; //如果 x和 y的代表元一致，说明他们共属同一集合，则不需要合并，直接返回；否则，执行下面的逻辑 if(rank[x]>rank[y]) pre[y]=x; //如果 x的高度大于 y，则令 y的上级为 x else //否则 {
if(rank[x]==rank[y]) rank[y]++; //如果 x的高度和 y的高度相同，则令 y的高度加1 pre[x]=y; //让 x的上级为 y } }
7. 总结
下面给出上述所有内容的代码汇总：
const int N=1005 //指定并查集所能包含元素的个数（由题意决定） int pre[N]; //存储每个结点的前驱结点 int rank[N]; //树的高度 void init(int n) //初始化函数，对录入的 n个结点进行初始化 {
for(int i = 0; i < n; i++){
pre[i] = i; //每个结点的上级都是自己 rank[i] = 1; //每个结点构成的树的高度为 1 } } int find(int x) //查找结点 x的根结点 {
if(pre[x] == x) return x; //递归出口：x的上级为 x本身，则 x为根结点 return find(pre[x]); //递归查找 } int find(int x) //改进查找算法：完成路径压缩，将 x的上级直接变为根结点，那么树的高度就会大大降低 {
if(pre[x] == x) return x; //递归出口：x的上级为 x本身，即 x为根结点 return pre[x] = find(pre[x]); //此代码相当于先找到根结点 rootx，然后 pre[x]=rootx } bool isSame(int x, int y) //判断两个结点是否连通 {
return find(x) == find(y); //判断两个结点的根结点（即代表元）是否相同 } bool join(int x,int y) {
x = find(x); //寻找 x的代表元 y = find(y); //寻找 y的代表元 if(x == y) return false; //如果 x和 y的代表元一致，说明他们共属同一集合，则不需要合并，返回 false，表示合并失败；否则，执行下面的逻辑 if(rank[x] > rank[y]) pre[y]=x; //如果 x的高度大于 y，则令 y的上级为 x else //否则 {
if(rank[x]==rank[y]) rank[y]++; //如果 x的高度和 y的高度相同，则令 y的高度加1 pre[x]=y; //让 x的上级为 y } return true; //返回 true，表示合并成功 }
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/199534.html原文链接：https://javaforall.net
