带权并查集模板

#include<cstdio> #include<iostream> using namespace std; int f[30005],d[30005],s[30005]; int find(int x) { if(f[x]==x)return x; int tmp=find(f[x]); d[x]+=d[f[x]]; return f[x]=tmp; } void move(int x,int y) { int sx=find(x); int sy=find(y); if(sx==sy)return ; f[sx]=sy; d[sx]=s[sy]; s[sy]+=s[sx]; } void search(int x) { find(x); printf("%d\n",d[x]); } int main() { int q; scanf("%d",&q); for(int i=1;i<=30000;i++) { f[i]=i; d[i]=0; s[i]=1; } while(q--) { char pd; cin>>pd; if(pd=='M') { int x,y; scanf("%d%d",&x,&y); move(x,y); } else if(pd=='C') { int x; scanf("%d",&x); search(x); } } return 0; }