传送门
题意：现在有n个立方体，n个坑。有p种操作，分为M与C。对于M操作：给出x，y，需要把x立方体所在的坑里的立方体全部搬到y立方体所在的坑上。对于C操作，给出x，需要输出x立方体下面的立方体个数。
Solution: 考虑权值并查集。 我们需要维护father[i]，代表i号立方体最下面的根节点。还需要维护cnt[i]，代表i号立方体下面的个数。 但是我们会发现，就算很好在getfather时更新father与cnt，却难以对于每个操作动态维护cnt（比如现在找到了root_x,root_y,想要更新cnt[root_x]就得加上root_y所在坑的个数。） 因此，我们还得维护size，size[x]代表以x为根的坑里有多少个立方体，这样才方便更新cnt。
#include<iostream> #define N 100005 using namespace std; int n,cnt[N],size[N],father[N]; int getfather(int x) { if(father[x]==x) return x; int fa=father[x]; father[x]=getfather(father[x]); cnt[x]+=cnt[fa]; return father[x]; } int main() { cin>>n; for(int i=1;i<=n;i++) { father[i]=i; cnt[i]=0; size[i]=1; } for(int i=1;i<=n;i++) { char opt; int x,y; cin>>opt; if(opt=='M')//move { cin>>x>>y; int ax=getfather(x); int bx=getfather(y); if(ax!=bx) { father[ax]=bx; cnt[ax]+=size[bx]; size[bx]+=size[ax]; size[ax]=0; } } if(opt=='C')//count { cin>>x; getfather(x);//更新一下cnt cout<<cnt[x]<<endl; } } return 0; }转载于:https://www.cnblogs.com/Patrickpwq/articles/9384820.html
