《算法竞赛进阶指南》0x41并查集 银河英雄传说（边带权并查集）
题目链接：https://www.acwing.com/problem/content/240/
题目给出初始时刻的n个队伍，每个队伍只有一个对应编号的i，操作有两种，一种是将第i列的接在第j列后面，一种是查询两个人是否在同一列，在同一列的话给出两者之间隔了多少人。
由于每一列都是一棵树，所以可以通过并查集进行求解，期间需要维护x到fx的距离，注意：每次fx改变的时候就要维护dx,并且需要一个辅助数组sizex在根节点计算树的大小。
代码：
#include<iostream> #include<cstdio> using namespace std; const int maxn = 30010; int f[maxn],siz[maxn]; int d[maxn];//d[x]表示的是x到fx的路径长度 int n; int find(int x){ if(x==f[x])return x; int root=find(f[x]); d[x]+=d[f[x]];//在没有路径压缩的情况下，d[x]表示的是指向前面结点的路径长度 return f[x]=root; } void merge(int x,int y){//将x拼接到y后面 int fx=find(x); int fy=find(y); if(x==y)return ; f[fx]=fy;//只有当fx改变的时候才改变d d[fx]=siz[fy]; siz[fy]+=siz[fx]; } int main(){ cin>>n; for(int i=1;i<=maxn-1;i++)f[i]=i,siz[i]=1; string s; int a,b; for(int i=1;i<=n;i++){ cin>>s>>a>>b; if(s[0]=='M')merge(a,b); if(s[0]=='C'){ if(find(a)==find(b))printf("%d ",abs(d[a]-d[b])-1); else puts("-1"); } } return 0; }