视频链接:
P1196 [NOI2002] 银河英雄传说 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
// 带权并查集 #include <iostream> using namespace std; const int N=30005; int T; int p[N],d[N],siz[N]; int find(int x){ if(p[x]==x) return x; int t=find(p[x]); //记录新根t d[x]+=d[p[x]]; //先更新x到新根t的距离 return p[x]=t; //再更新p[x],路径压缩 } int main(){ for(int i=1;i<N;i++) p[i]=i,siz[i]=1; scanf("%d",&T); while(T--){ char op; int x,y; scanf("%s %d%d",&op,&x,&y); if(op=='M'){ int px=find(x),py=find(y); p[px]=py; //x队列接在y队列后面 d[px]=siz[py]; //更新 px到py 的距离 siz[py]+=siz[px]; //在根上记录队列大小 } else{ if(find(x)!=find(y)) puts("-1"); else printf("%d\n",abs(d[x]-d[y])-1); } } }
标签:查集,int,新根,带权,NOI2002,P1196 From: https://www.cnblogs.com/dx123/p/18211426