原题
把两个舰队合并起来，查询某两个舰是否在同一舰队中，简单用一下并查集就可以了。
但本题不限于此，还需要求两个舰的距离，那么试试改并查集，并查集最大的特点就是利用祖先，那么他们的距离就可以用到祖先的距离差表示。
现在的问题是求某点到其祖先的距离，一定不能取消路径压缩计算次数，铁定超时。
开一个数组front[i]表示i点到祖先的距离，典型的加权并查集，在路径压缩时进行修改（详见代码）。
#include<iostream> #include<cstdio> #include<cstring> #include<iomanip> #include<algorithm> using namespace std; int n;int father[30001],front[30001],hou[30001]; int find(int x) { if(x==father[x]) return x; int k=find(father[x]); front[x]=front[x]+front[father[x]]; return father[x]=k; } int main() { cin>>n; for(int i=1;i<=30000;++i) { father[i]=i;front[i]=0;hou[i]=1; } for(int i=1;i<=n;++i) { char a; cin>>a; int x,y; scanf("%d%d",&x,&y); if(a=='M') { int fx=find(x); int fy=find(y); father[fx]=fy; front[fx]=hou[fy]; hou[fy]+=hou[fx]; } else { if(find(x)==find(y)) { int t=abs(front[x]-front[y])-1; printf("%d\n",t); } else printf("-1\n"); } } return 0; }
