题意
有n个箱子，编号从1到n,初始时每个箱子单独为一列；
接下来有p行输入，M, x, y 或者 C, x；
对于M,x,y：表示将编号x的箱子所在的一列箱子搬到编号的y箱子所在的一列箱子上；
对于C,x：表示求箱子编号x的箱子下面有多少个箱子；
Sample Input
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
Sample Output
1
0
2
思路
需要创建三个数组，一个fa[i] 记录i的父亲,也就是栈的底部，一个sum[i]记录每个栈中箱子的个数（主要是记录根节点的），还有一个under[i] 用于记录当前编号i的下方有多少个箱子
初始化操作
for( int i = 0 ; i <= n ; i ++)
{fa[i] = i ;
sum[i] = 1;
under[i] = 0;
}
merge操作
假设现在执行Merge(a,b),把a放在b的上面，我先要找出x,y的根节点，x,y，很显然fa[x]=y;
想一下 under[x] 是多少, 那肯定是旧的sum[y]的大小 ，即 under[x]=sum[y];
在想一下sum[y]怎么更新，新的sum应该等于旧的sum[y]+=sum[x];
void merge(int a,int b)
{
int x=find(a);
int y=find(b);
//把x 放到 y上 ，fa[x] =y;
if(x!=y)
{
fa[x] = y;
under[x] = sum[y];
sum[y] += sum[x];
}
}
find操作
如何去修改上面合并 利用剩下的不正确的under[i]。
每个编号的under都 与移动合并前的栈 的根结点存在联系。对于当前要处理的v结点，其正确的under应该等于它合并之前的under加上它合并之前栈A的根结点的under。即under[v] += under[f[v]]。
int find(int x)
{
if(fa[x] == x)
return x;
else
{
int temp = find(fa[x]);
under[x] += under[fa[x]];
return fa[x] = temp;
}
}
完整代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <map>
#include <queue>
#include <vector>
#define endl '\n'
using namespace std;
void IOS(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
typedef pair<int,int> PII;
typedef long long ll;
const int maxn=1e5+5;
int sum[maxn];
int under[maxn];
int fa[maxn];
int find(int x)
{
if(fa[x] == x)
return x;
else
{
int temp = find(fa[x]);
under[x] += under[fa[x]];
return fa[x] = temp;
}
}
void merge(int a,int b)
{
int x=find(a);
int y=find(b);
//把x 放到 y上 ，fa[x] =y;
if(x!=y)
{
fa[x] = y;
under[x] = sum[y];
sum[y] += sum[x];
}
}
char s[2];
int main(){
int t;
scanf("%d", &t);
int n = 30005;
for( int i = 0 ; i <= n ; i ++)
{fa[i] = i ;
sum[i] = 1;
under[i] = 0;
}
while(t--)
{
cin>>s;
if(s[0] == 'C')
{
int q;
scanf("%d" , &q);
find(q);//一定要更新一下，q的under可能不正确，所以必须要重新修改确认一遍
printf("%d\n" , under[q]);
}
else if(s[0] == 'M')
{
int x,y;
scanf("%d%d" , &x , &y);
merge(x , y);
}
}
return 0;
}