首页 > 程序开发 > 软件开发 > 其他 >

hdoj 2818题目解答

2017-02-16

hdoj 2818题目解答:john 正在玩积木,有N个积木编号为1、、、N,分成N堆,每堆只包含一个积木,然后做P次操作,操作分为2种。

hdoj 2818题目解答:john 正在玩积木,有N个积木编号为1、、、N,分成N堆,每堆只包含一个积木,然后做P次操作,操作分为2种。

M X Y:把包含X的一堆放到包含Y的一堆上,如果XY同在一堆上,不做处理。C X:计算出X积木下边有多少个积木
每次遇到C操作,输出数量。

解题思路:

并查集问题

代码如下:

#include
int r[30002],h[30002],l[30002];
int root(int block)
{
  int tem;
  if(h[block]==0) return block;
  tem=root(r[block]);
  h[block]=h[block]+h[r[block]];
  r[block]=tem;
  return tem;
}
int main(void)
{
  int i,x,P,y;
  char ch;
  scanf("%d",&P);
  for(i=0;i<=30000;i++)
  {
    r[i]=i;
    h[i]=0;
    l[i]=1;
  }
  while(P--)
  {
     getchar();
     scanf("%c",&ch);
     if(ch==&#39;M&#39;)
     {
       scanf("%d%d",&x,&y);
       if(root(x)==root(y)) continue;
       if(x!=r[x])
       {
         r[r[x]]=r[y];
         h[r[x]]=l[r[y]];
         l[r[y]]+=l[r[x]];
         h[x]=h[x]+h[r[x]];
         r[x]=r[y];
       }
     else
     {
       h[x]=l[r[y]];
       r[x]=r[y];
       l[r[y]]+=l[x];
     }
   }
   else
   {
     scanf("%d",&x);
     root(x);
     printf("%d\n",h[x]);
   }
  }
  return 0;
}
相关文章
最新文章
热点推荐