poj.1988并查集-路径压缩、更新结点（偏移量）

本文主要是介绍poj.1988并查集-路径压缩、更新结点（偏移量），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述很简单就是有N个盒子，标号分别为1-N，现有两种操作，一种是移动，将包含x的整体方块移到包含y的整体方块的上方，注意是整体移动，另一种为读取操作，输出在x下方方块的个数，那么对于这题感觉就是并查集路径压缩以及更新结点的典型，我们定义一个偏移量代表子节点与根节点的距离，然后定义一个son数组代表x下方的结点的个数，这样用根节点的son--所求结点的偏移量-1 就是x下方的方块数量了：下面是代码：

#include <stdio.h>
#include <stdlib.h>
#define Max 30001
int pre[Max];
int son[Max];
int set[Max];
int find(int x){if(x==set[x])return x;int temp=set[x];set[x]=find(set[x]);pre[x]+=pre[temp];return set[x];
}
int p;
int main()
{scanf("%d",&p);for(int i=1;i<Max;i++){pre[i]=0;son[i]=1;set[i]=i;}int a,b,c,x,y;while(p--){getchar();if(getchar()=='M'){scanf("%d%d",&a,&b);x=find(a);y=find(b);set[y]=x;pre[y]=son[x];son[x]+=son[y];}else{scanf("%d",&c);printf("%d\n",son[find(c)]-pre[c]-1);}}return 0;
}

 

注意要更新结点的偏移量。

这篇关于poj.1988并查集-路径压缩、更新结点（偏移量）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---