下载掌阅APP，畅读海量书库
立即打开
题目描述（POJ1988）： 贝西正在玩方块游戏，方块编号为1～ N （1≤ N ≤30,000），开始时每个方块都相当于一个栈。贝西执行 P 个（1≤ P ≤100,000）操作，操作类型有两种：M X Y ，将包含 X 的栈整体移动到包含 Y 的栈顶部；C X ，查询 X 方块下的方块数量。请统计贝西每个操作的结果。
输入： 第1行为单个整数 P ，表示操作的数量。第2～ P +1行：每一行都描述一个操作（注意： N 的值不会出现在输入文件中，没有一种移动操作会请求将栈移动到自身）。
输出： 对每个C操作，都输出统计结果。
题解： 本题包括移动和计数两种操作，方块的整体移动可以使用二维数组实现，但是操作数量很大，若一个一个地移动，则会超时。整体移动相当于集合的合并，因此可以借助并查集实现，在集合查找和合并时，更新树根下方的方块数量即可。使用并查集可以快速、高效地解决该问题。
（1）初始化。初始化每个方块的集合号都为其自身。
（2）查询或者合并。
· C X ：查询 X 的集合号，并输出 X 方块下的方块数量。 d [ i ]表示第 i 个方块下的方块数量。查询 X 的祖宗，在返回过程中将经过路径上节点的集合号统一为祖宗的集合号，将当前节点的 d 值加上其父节点的 d 值。
· M X Y ：合并 X 、 Y 集合号。cnt[ i ]表示第 i 个栈的方块数量。首先找到 X 、 Y 所在的集合祖宗 a 、 b ，然后将 a 的集合号修改为 b ，fa[ a ]= b ，更新 d [ a ]=cnt[ b ]，cnt[ b ]+=cnt[ a ]。
（1）初始化。根据输入样例，初始时每个方块的集合号都为其自身，fa[ i ]= i ；在每个方块下都有0个方块， d [ i ]=0；每个栈只有1个方块，cnt[ i ]=1。
（2）合并。M 1 6：将包含1的栈整体移动到包含6的栈。首先找到1和6的祖宗1、6，然后将1的集合号修改为6，fa[1]=6，更新 d [1]=cnt[6]=1，cnt[6]+=cnt[1]=2。
（3）查询。C 1：查询1下面有多少个方块。首先查询1的集合号，找祖宗，在查询过程中将当前节点的 d 值加上其父节点的 d 值， d [1]+= d [6]=1。
（4）合并。M 2 4：将包含2的栈整体移动到包含4的栈。首先找到2和4的祖宗2、4，然后将2的集合号修改为4，fa[2]=4，更新 d [2]=cnt[4]=1，cnt[4]+=cnt[2]=2。
（5）合并。M 2 6：将包含2的栈整体移动到包含6的栈。首先找到2和6的祖宗4、6，然后将4的集合号修改为6，fa[4]=6，更新 d [4]=cnt[6]=2，cnt[6]+=cnt[4]=4（注意：只修改祖宗集合号，2号方块的集合号及 d 值并没有修改，下次查询2的集合号时才会更新。这正是并查集的妙处）。
（6）查询。C 3：查询3下面有多少个方块。首先查询到3的集合号为3， d [3]=0。
（7）查询。C 4：查询4下面有多少个方块。首先查询4的集合号，在查询过程中将当前节点的集合号修改为其父节点的集合号，将当前节点的 d 值加上其父节点的 d 值， d [4]+= d [6]=2。
（8）若继续查询C 2，则查询2下面有多少个方块。先查询2的祖宗，在返回过程中将当前节点的 d 值加上其父节点的 d 值， d [2]+= d [4]=3。
（1）初始化。
（2）查询。查询 x 的集合号，集合号等于自身时停止。在返回过程中，将经过路径上节点的集合号都统一为祖宗的集合号，将当前节点的 d 值加上其父节点的 d 值。
（3）合并。首先找到 x、y 所在的集合祖宗 a 、 b ，然后将 a 的集合号修改为 b ，更新 d [ a ]=cnt[ b ]，cnt[ b ]+=cnt[ a ]。
