POJ 1988 解题报告

解题的关键是考虑，如果是C，那么查询的时候该怎么操作？如果是sum[find(x)]-up[x]-1,那么这道题就可以解决了。
因此解题的关键是找到满足题目要求的那个功能是怎么结合并查集的特点去实现。

Source Code

Problem: 1988		User: omycle
Memory: 616K		Time: 1110MS
Language: C++		Result: Accepted

• Source Code
  

  #include <iostream>
  using namespace std;
  const int SIZE=30000;
  int sum[SIZE+1];
  int up[SIZE+1];
  int parent[SIZE+1];
  int digui(int x);
  int find(int x)
  {
  int r=x;
  while(parent[r]!=r)
  {
    r=parent[r];
  }/*一路找到根节点，返回*/
  //开始压缩路径了
  while(parent[x]!=r)
  {
  int temp=parent[x];
  //改变其up值
    up[x]=digui(x);
    parent[x]=r;
    x=temp;
  }
  return r;
  }
  int digui(int x)
  {
  int r=x;
  while(parent[r]!=r)
  {
    r=parent[r];
  }
  if(parent[x]==r)
  return up[x];
  else
  return up[x]+digui(parent[x]);
  }/*求得其up值*/
  void uniontwo(int a,int b)
  {
    a=find(a);
    b=find(b);
   parent[b]=a;
  //下面，因为a在b的上面，所以需要改变a的sum[]改变b的up
   up[b]=sum[a];
   sum[a]+=sum[b];
  }
  int main()
  {
  int n;
   cin>>n;
  for(int k=1;k<=SIZE;k++)
  {
    sum[k]=1;
    up[k]=0;
    parent[k]=k;
  }
  for(int i=1;i<=n;i++)
  {
  char a;
    cin>>a;
  if(a=='M')
  {
  int b,c;
     cin>>b>>c;
  uniontwo(b,c);
  }
  if(a=='C')
  {
  int d;
     cin>>d;
     cout<<sum[find(d)]-up[d]-1<<endl;
  }
  }
  return 0;
  }