luogu1196 银河英雄传说 (并查集)

并查集,不仅记fa,还记与fa的距离,还记根对应的尾节点

路径压缩的时候更新那个距离就行了

 #include<bits/stdc++.h>
#define pa pair<int,int>
#define CLR(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
const int maxn=3e4+; inline ll rd(){
ll x=;char c=getchar();int neg=;
while(c<''||c>''){if(c=='-') neg=-;c=getchar();}
while(c>=''&&c<='') x=x*+c-'',c=getchar();
return x*neg;
} int fa[maxn],tl[maxn],dis[maxn],T,N=; inline int getf(int x){
if(x==fa[x]) return x;
int re=getf(fa[x]);
dis[x]+=dis[fa[x]],fa[x]=re;
return re;
} inline void add(int x,int y){
int a=getf(x),b=getf(y);
fa[a]=tl[b],tl[b]=tl[a],dis[a]=;
} int main(){
// freopen("testdata.in","r",stdin);
int i,j,k;
T=rd();
for(i=;i<=N;i++)
tl[i]=fa[i]=i;
for(i=;i<=T;i++){
char s[];scanf("%s",s);
int a=rd(),b=rd();
if(s[]=='M') add(a,b);
else{
int x=getf(a),y=getf(b);
if(x!=y) printf("-1\n");
else printf("%d\n",abs(dis[a]-dis[b])-);
}
}
return ;
}
上一篇:[JavaScript] 后端js的模块化规范CommonJs


下一篇:(转) 前端模块化:CommonJS,AMD,CMD,ES6