并查集11分求助
查看原帖
并查集11分求助
151647
sycqwq楼主2021/10/18 21:32

rtqwq

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4+5;
int t;
int f[maxn],d[maxn],siz[maxn];
int getfa(int x)
{
    if(f[x]==x)
        return x;
    d[x]+=d[f[x]];
    return f[x]=getfa(f[x]);
}
void merge(int x,int y)
{
    int fx=getfa(x),fy=getfa(y);
    f[fx]=fy;
    d[fx]=siz[fy];
    // cout<<d[fx]<<' '<<fx<<endl;
    siz[fy]+=siz[fx];
}
int main()
{
    cin>>t;
    for(int i=1;i<=maxn-1;i++)
    {
        f[i]=i;
        siz[i]=1;
    }
    for(int i=1;i<=t;i++)
    {
        char op;
        int x,y;
        cin>>op;
        cin>>x>>y;
        if(op=='M')
        {
            merge(x,y);
        }
        else
        {
            // cout<<getfa(x)<<' '<<getfa(y)<<endl;
            if(getfa(x)!=getfa(y))
                cout<<-1<<endl;
            else
                cout<<abs(d[x]-d[y])-1 <<endl;
        }
    }
    return 0;
}
2021/10/18 21:32
加载中...