題目分析：
帶權并查集板子題，之前沒有見過，
本題需要維護兩個值，一個是是否聯通，還有一個是每一艘船到當前隊頭的距離，
考慮在一般并查集的基礎上額外維護兩個值，一個是到隊頭的距離，另一個是當前整個隊伍的長度，后者用來在合并時計算前者的，
更具體的：
合并時，將放在后面的隊頭的隊頭距離加上放在前面的隊伍的長度并將兩個隊伍的長度合并，
查詢的時候，記錄下原來父節點的值，然后查詢父節點，在路徑壓縮的時把自己到隊頭的距離加上父節點到隊頭的距離并更新所在的隊伍長度，
關于最后一條的順序問題，這是因為可能有多條路徑等待壓縮，需要先一次壓完然后再加，而且加完后這個點就連到了根節點，也就不用擔心會反復加了，
代碼：
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int T,fa[30005],front[30005],num[30005],x,y;
char c;
int find(int now){
if(fa[now]==now)return now;
int k=fa[now];
fa[now]=find(fa[now]);
front[now]+=front[k];
num[now]=num[fa[now]];
return fa[now];
}
int main(){
scanf("%d",&T);
for(int i=1;i<=30000;i++)
fa[i]=i,num[i]=1;
while(T--){
cin>>c;
if(c=='M'){
scanf("%d%d",&x,&y);
int fx=find(x),fy=find(y);
fa[fx]=fy;
front[fx]+=num[fy];
num[fx]+=num[fy];
num[fy]=num[fx];
}
else{
scanf("%d%d",&x,&y);
if(find(x)!=find(y))printf("-1\n");
else
printf("%d\n",abs(front[x]-front[y])-1);
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/306021.html
標籤：其他
上一篇：Flagggggg