poj 1988-白红宇

poj 1988

阅读量：5741 次

发布时间：2019-06-18

本文共 1063 字，大约阅读时间需要 3 分钟。

题目：M指的是将前一个箱子移动到后一个箱子上,C为询问在这个箱子下面的箱子有多少个？

这里sum指的是这个并查集中的元素的个数。rank为到根节点的距离（可以压缩更新），p为上一个根节点.

View Code

#include
      
        #include
       
         #include
        
          #include
          using namespace std; const int maxn=100005; int n,m; int p[maxn],rank[maxn],sum[maxn]; void init() {
    for(int i=0;i<=30005;i++)     {
            p[i]=i;         rank[i]=0;         sum[i]=1;     } } int find(int x) {
    if(x==p[x]) return x; int t=find(p[x]);     rank[x]=rank[x]+rank[p[x]];     p[x]=t; return t; } int main() {
    int x,y;char str[3];     init();     scanf("%d",&n); while(n--)     {
            scanf("%s",str); if(str[0]=='M')         {
                scanf("%d%d",&x,&y); int tx=find(x); int ty=find(y);             p[tx]=ty;             rank[tx]+=sum[ty];             sum[ty]+=sum[tx];         } else if(str[0]=='C')         {
                scanf("%d",&x);             find(x);             printf("%d\n",rank[x]);         }     } return 0; }