题目：https://www.lydsy.com/JudgeOnline/problem.php?id=3376
带偏移量的并查集。
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=3e4+5,M=1e5+5; int n,m,x[M],y[M],fa[N],dis[N],siz[N]; char op[M]; int rdn() { int ret=0;bool fx=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')fx=0;ch=getchar();} while(ch>='0'&&ch<='9') ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar(); return fx?ret:-ret; } int g[20]; void wrt(int x) { if(x<0)putchar('-'),x=-x; if(!x)putchar('0'); int t=0; while(x)g[++t]=x%10,x/=10; while(t)putchar(g[t]+'0'),t--; puts(""); } int find(int a) { if(fa[a]==a)return a; int x=find(fa[a]); dis[a]+=dis[fa[a]]; return fa[a]=x; } int main() { m=rdn(); for(int i=1;i<=m;i++) { op[i]=getchar(); while(op[i]!='C'&&op[i]!='M')op[i]=getchar(); x[i]=rdn(); n=max(n,x[i]); if(op[i]=='M')y[i]=rdn(),n=max(n,y[i]); } for(int i=1;i<=n;i++)fa[i]=i,siz[i]=1; for(int i=1;i<=m;i++) { if(op[i]=='M') { int u=find(x[i]),v=find(y[i]); dis[v]=siz[u]; fa[v]=u; siz[u]+=siz[v]; } else { int d=find(x[i]); wrt(siz[d]-1-dis[x[i]]); } } return 0; }