此题为带边权的并查集
有一个划分为 N 列的星际战场，各列依次编号为 1,2,…,N 。
有 N 艘战舰，也依次编号为 1,2,…,N ，其中第 i 号战舰处于第 i 列。
有 T 条指令，每条指令格式为以下两种之一：
M i j，表示让第 i 号战舰所在列的全部战舰保持原有顺序，接在第 j 号战舰所在列的尾部。
C i j，表示询问第 i 号战舰与第 j 号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。
现在需要你编写一个程序，处理一系列的指令。
输入格式
第一行包含整数 T ，表示共有 T 条指令。
接下来 T 行，每行一个指令，指令有两种形式：M i j 或 C i j。
其中 M 和 C 为大写字母表示指令类型， i 和 j 为整数，表示指令涉及的战舰编号。
输出格式
你的程序应当依次对输入的每一条指令进行分析和处理：
如果是 M i j 形式，则表示舰队排列发生了变化，你的程序要注意到这一点，但是不要输出任何信息；
如果是 C i j 形式，你的程序要输出一行，仅包含一个整数，表示在同一列上，第 i 号战舰与第 j 号战舰之间布置的战舰数目，如果第 i 号战舰与第 j 号战舰当前不在同一列上，则输出 ?1 。
数据范围
N≤30000,T≤500000
输入样例：
4
M 2 3
C 1 2
M 2 4
C 4 2
输出样例：
-1
1
本题要求的是能够求两个战舰之间的距离关系，那如果每次都直接找过去的话明显会超时，那我们可以换一下思路，我们记录每个点到根节点的距离，再距离相减就是两个战舰的距离了。所有我们需要一个记录距离的数组d[];
还有一个问题就是我们连接两个舰队的时候，距离会被打乱。那我们还需要记录舰队的大小size，这样我们就只要一下多了多少的距离，来更新我们的d[]数组。
我们需要在标准的并查集中进行一下更改
1.find函数
我们在find函数里来更新每个点到根节点的距离。先找到根节点，在把当前节点指向根节点的同时加上父节点到根节点的距离，从而更新距离
int t[30010],d[30010],size[30010];
int find(int x)
{
if(x==t[x]) return x;int root=find(t[x]);d[x]+=d[t[x]];return t[x]=root;
}
2.memge函数
在连接两个舰队的时候，我们后面的那个舰队的根节点的距离就要加上前面舰队的大小
这时两个舰队合二为一，前面舰队的大小就要加上一个后面舰队的大小
void memge(int a,int b)
{
int x=find(a),y=find(b);t[x]=y;d[x]+=size[y];size[y]+=size[x];
}
以下为完整代码
#include "bits/stdc++.h"
using namespace std;
int n;
int t[30010],d[30010],size[30010];//d数组表示距离，size数组表示大小
int find(int x)
{
if(x==t[x]) return x;int root=find(t[x]);d[x]+=d[t[x]];return t[x]=root;
}
void memge(int a,int b)
{
int x=find(a),y=find(b);t[x]=y;d[x]+=size[y];size[y]+=size[x];
}
int main()
{
cin>>n;for(int i=1;i<=30010;i++) {
t[i]=i;size[i]=1;}while(n--){
char a;int j,k;cin>>a>>j>>k;if(a=='M'){
memge(j,k);}else if(a=='C'){
if(find(j)!=find(k)) cout<<-1<<endl;else cout<<abs(d[j]-d[k])-1<<endl;}}
}
此外，并查集的高级用法还有拓展域的并查集，感兴趣的话可以去看看。
放个传送门，嘿嘿
食物链(拓展域的并查集)