由于并查集让我很自闭（其实是我太弱了）,所以学习了加权并查集，这是例题：
题目链接：P1196 [NOI2002]银河英雄传说
不是很简单，但对于大佬还是签到题。
合并与路径压缩时直接维护\(dis[],num[]\)，就好了，不过为什么要引进\(num[]\)呢？
真无奈。
不过++此题就很简单了，注意\(getf()\)有两句不要写反，否则就\(10\;pts\)了。一会代码里有标注。
复杂度是\(O(n\alpha(n))\)(其实我也不知道是这个吗，差不多就行了)
\(Code\):
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=30005;
int f[MAXN],dis[MAXN],num[MAXN];
void init(int m){for(int i=1;i<=m;i++) f[i]=i,dis[i]=0,num[i]=1;}
int getf(int u)
{
if(f[u]==u) return u;
else
{
int now=f[u];
f[u]=getf(f[u]);//这句和下句反了会炸，为什么呢？
dis[u]+=dis[now];//注意dis是加，放过来事实上会加两次，就WA了。
num[u]=num[f[u]];
}
return f[u];
}
void merge(int u,int v)
{
int t1=getf(u),t2=getf(v);
if(t1!=t2)
{
f[t2]=t1;
dis[t2]=num[t1];
num[t2]+=num[t1];
num[t1]=num[t2];
}
return;
}
int n,l,r;
char flag;
int main()
{
init(MAXN);
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>flag>>l>>r;
if(flag=='M') merge(l,r);
else if(flag=='C')
{
int g=getf(l),h=getf(r);
if(g!=h)
{
printf("-1\n");
continue;
}
else printf("%d\n",abs(dis[l]-dis[r])-1);
}
}
return 0;
}
等再有道加权并查集，再写写心得？