题目大意
开始有N堆砖块,编号为1,2....N,每堆都只有一个。之后可以进行两种操作:
(1)M X Y 将编号为X的砖块所在的那堆砖拿起来放到编号为Y的砖块所在的堆上;
(2)C X 查询编号为X的砖块所在的堆中,在砖块X下方的所有砖块的数目
题目分析
典型的集合合并和查询,因此采用并查集。并查集的基本框架就是一个GetPar函数(实现查找集合的祖先,同时实现路径压缩),一个Union函数(实现将两个集合合并),一个SameGroup函数(判断两个元素是否属于同一个集合)。
在利用并查集解决具体问题的时候,需要做的是设置一个数据结构用于存放问题所需要的信息,然后在GetPar函数和Union函数中更新这个数据结构。
在本题中,维护信息 SumOfStack(每堆中的所有砖块数目),NumOfUnderBlock(堆中在砖块下方的砖块数目)。将每堆砖块集合的编号(即集合的根)设置为该堆最下方的砖块号,则在合并的时候,上堆的根节点的父节点设置为下堆的根节点,可以更新的数据为上堆的根节点下方的砖块数目
和下堆的根节点代表的堆总砖块数
。
这样,每堆的根节点的SumOfStack信息是正确的,而每次合并后上堆的原根节点的NumOfUnderBlock信息也是正确的;对于某个砖块b,在GetPar的过程中,由于b的gPar[b]可能没被更新,如果没被更新,则b的NumOfUnderBlock[b]表示在b之前所在的堆中位于b下方的砖块数目
也是正确的,于是将此时的NumOfUnderBlock[b] + NumOfUnderBlock[gPar[b]](注意,这里的gPar[b]为b原来的堆中的根),即可得到最终的NumOfUnderBlock[b],这可以在GetPar函数的递归中完成。
实现(c++)
#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #define MAX_STACK_NUM 30001 int gPar[MAX_STACK_NUM]; int gSumOfStack[MAX_STACK_NUM]; int gNumOfUnderBlock[MAX_STACK_NUM]; int GetPar(int c){ if (c != gPar[c]){ int p = gPar[c]; gPar[c] = GetPar(gPar[c]); //信息维护 gNumOfUnderBlock[c] += gNumOfUnderBlock[p]; } return gPar[c]; } void Union(int a, int b){ int p1 = GetPar(a); int p2 = GetPar(b); gPar[p1] = p2; //信息维护 gNumOfUnderBlock[p1] = gSumOfStack[p2]; gSumOfStack[p2] += gSumOfStack[p1]; } void Init(){ for (int i = 0; i < MAX_STACK_NUM; i++){ gSumOfStack[i] = 1; gNumOfUnderBlock[i] = 0; gPar[i] = i; } } int main(){ int p, X, Y; scanf("%d", &p); char op; Init(); for (int i = 0; i < p; i++){ getchar(); scanf("%c", &op); if (op == 'M'){ scanf("%d %d", &X, &Y); Union(X, Y); } else if (op == 'C'){ scanf("%d", &X); GetPar(X); printf("%d ", gNumOfUnderBlock[X]); } } return 0; }