大佬看看窝的并查集写错了吗
查看原帖
大佬看看窝的并查集写错了吗
124143
Countjoyyauldly楼主2020/7/20 16:34
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
using namespace std;
int n;
int c2,c3;
char c1;
int f[10005];
int d[10005];
int cnt[10005];
int find(int r)
{
    if(f[r]!=r)
    {
        int t=f[r];
        f[r]=find(f[r]);
        d[r]+=d[t];
    }
        return f[r];
}
int main()
{
    memset(d,1,sizeof(d));
    memset(cnt,1,sizeof(cnt));
    cin>>n;
     for(int i=1;i<=30000;i++)
            f[i]=i;
    while(n--)
    {
        cin>>c1>>c2>>c3;
        if(c1=='M')
        {
            int fx=find(c2);
            int fy=find(c3);
            if(find(fx)!=find(fy))
            {
                f[fx]=fy;
            d[fx]=cnt[fy];
            cnt[fy]+=cnt[fx];
            }
        }
        else
            {
                int fx=find(c2);
                int fy=find(c3);
                if(fx!=fy) cout<<"-1"<<endl;
                else
                {
                    cout<<abs(d[c2]-d[c3])-1<<endl;
                }
            }
    }
    return 0;
}

2020/7/20 16:34
加载中...