并查集12分求救
查看原帖
并查集12分求救
219935
JeffWang2019楼主2020/6/2 17:54

QWQQWQ

#include <bits/stdc++.h>
using namespace std;
char c;
int ans[30001],fa[30001],st[30001];
int t,p,q,to;
int find(int x)
{
    if(fa[x]==x)
    {
        return x;
    }
    st[x]+=st[fa[x]];
    fa[x]=find(fa[x]);
    return fa[x];
}
void merge(int x,int y)
{
    int fx=find(x),fy=find(y);
    fa[fy]=fx;
    st[fy]=ans[fx];
    ans[fx]+=ans[fy];
    ans[fy]=0;
}
int main()
{
    for(int i=1;i<=30000;i++)
    {
        ans[i]=1;
        fa[i]=i;
    }
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        cin>>c>>p>>q;
        if(c=='M')
        {
            merge(q,p);
        }
        else
        {
            if(find(p)==find(q))
            {
                to=fabs(st[p]-st[q])-1;
                printf("%d\n",to);
            }
            else
            {
                printf("-1\n");
            }
        }
    }
    return 0;
}
2020/6/2 17:54
加载中...