> 导论里最后有一个比这个稍复杂点的,说可以启发式,这个可以么?
可以. 弱弱的代码
#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <map>
#include <set>
using namespace std;

const int N = 30001;
const int M = 100001;

int nele[N];
int par[N];
int lenbtm[N];
int findset(int x){
  if(par[x]!=x){
    int rt = findset(par[x]);
    if(rt!=par[x]){
      lenbtm[x] += lenbtm[par[x]];
    }
    par[x] = rt;
  }
  return par[x];
}
void unionset(int topset, int btmset){
  if(nele[topset]>nele[btmset]){
    lenbtm[topset] += nele[btmset];
    lenbtm[btmset] -= lenbtm[topset];
    par[btmset] = topset;
    nele[topset] += nele[btmset];
  } else {
    lenbtm[topset] = lenbtm[topset] + nele[btmset] - lenbtm[btmset];
    par[topset] = btmset;
    nele[btmset] += nele[topset];
  }
}

int main(){
  for(int i=1;i<=N;++i){
    par[i] = i;
    lenbtm[i] = 0;
    nele[i] = 1;
  }
  int m;
  scanf("%d", &m);
  char op[3];
  for(int i=0;i<m;++i){
    scanf("%s", op);
    if(op[0]=='M'){
      int x,y;
      scanf("%d%d", &x, &y);
      int ts = findset(x);
      int bs = findset(y);
      unionset(ts,bs);
    } else {
      int x;
      scanf("%d", &x);
      int res;
      int xset = findset(x);
      if(xset==x) res = lenbtm[x];
      else res = lenbtm[x]+lenbtm[xset];
      printf("%d\n", res);
    }
  }
}