记录编号	586642	评测结果	AAAAAAAAAA
题目名称	[NOI 2002]银河英雄传说	最终得分	100
用户昵称	超人	是否通过	通过
代码语言	C++	运行时间	3.248 s
提交时间	2024-02-19 22:00:45	内存使用	18.15 MiB

#include<bits/stdc++.h>
using namespace std;
const int M=1e6;
int a,NOI1[M],NOI2[M],NOI3[M];
int income(int x)
{
    if(x==NOI1[x]) return x;
    int galaxy=income(NOI1[x]);
    NOI2[x]+=NOI2[NOI1[x]];
    return NOI1[x]=galaxy;
}
int main()
{
	freopen("galaxy.in","r",stdin);
	freopen("galaxy.out","w",stdout);
	for(int i=1;i<=M;i++)
	{
        NOI1[i]=i;
        NOI3[i]=1;
    }
    cin>>a;
    while(a--)
	{
        char op[M];
        int x,y;
        cin>>op;
        cin>>x>>y;
        int TA=income(x),TB=income(y);
        if(op[0]== 'M')
		{
            NOI1[TA]=TB;
            NOI2[TA]=NOI3[TB];
            NOI3[TB]+=NOI3[TA];
        }
        else
		{
            if(TA!=TB) cout<<"-1"<<endl;
            else cout<<abs(NOI2[x]-NOI2[y])-1<<endl;
        }
    }
	return 0;
}