C126 带权并查集 P1196 [NOI2002] 银河英雄传说

#include<bits/stdc++.h>
using namespace std;
int fa[110000], q[110000], z[110000];
// q[i]表示在第i个人所在队列中，第i个人的前面有多少人
// z[i]表示第i个人所在队列总人数 
int findfa(int x)
{
    if(x == fa[x]) return fa[x];
    int tx = findfa(fa[x]);
    q[x] = q[x] + q[fa[x]]; // 实时更新，重点理解为什么不是“q[x] = 1 + q[fa[x]];”
    return fa[x] = tx; // 每次findfa完后，x的fa[x]前面0个人 
}
int main()
{
    for(int i = 1; i <= 100000; i++) fa[i] = i, q[i] = 0, z[i] = 1;
    int t; scanf("%d", &t);
    while(t--)
    {
        int x, y; char s[10]; scanf("%s%d%d", s, &x, &y);
        int tx = findfa(x), ty = findfa(y);
        if(s[0] == 'M') // 表示x所在的队伍接入到y所在队伍的后面 
        {
            if(tx != ty)
            {
                fa[tx] = ty;
                q[tx] += z[ty];
                z[ty] += z[tx];
            }
        }
        else
        {
            if(tx != ty) printf("-1\n");
            else printf("%d\n", abs(q[x] - q[y]) - 1);
        }
    }
    return 0;
}

C126 带权并查集 P1196 [NOI2002] 银河英雄传说

【参考程序】
#include<bits/stdc++.h>
using namespace std;
int fa[110000],q[110000],z[110000];
//q[i]表示在第i个人所在队列中，第i个人的前面有多少人
//z[i]表示第i个人所在队列总人数
int findfa(int x)
{
if(xfa[x])return fa[x];
int tx=findfa(fa[x]);
q[x]=q[x] + q[fa[x]];//实时更新 ,重点理解为什么不是“q[x]=1 + q[fa[x]];”
return fa[x]=tx;//每次findfa完后，x的fa[x]前面0个人
}
int main()
{
for(int i=1;i<=100000;i++)fa[i]=i,q[i]=0,z[i]=1;
int t;scanf("%d",&t);
while(t--)
{
int x,y;char s[10];scanf("%s%d%d",s,&x,&y);
int tx=findfa(x),ty=findfa(y);
if(s[0]'M')//表示x所在的队伍接入到y所在队伍的后面
{
if(tx!=ty)
{
fa[tx]=ty;
q[tx]+=z[ty];
z[ty]+=z[tx];
}
}
else
{
if(tx!=ty)printf("-1\n");
else printf("%d\n",abs(q[x]-q[y])-1);
}
}
return 0;
}