求助
查看原帖
求助
68574
HGJH°L楼主2020/8/16 19:53

rt

#include<bits/stdc++.h>

using namespace std;

int n;
int f[30004];//根 
int dis[30004];//离队头的长度 
int len[30004];//队列的长度 
char c;
int p,q;
int fp,fq;
int i;
//int maxn;

int find(int x)
{
	if (f[x]!=x)
	{
		dis[x]+=dis[f[x]];
		f[x]=find(f[x]);
		len[x]=len[f[x]];
	}
	return f[x];
}

int abs(int x)
{
	return (x*=((x>=0)?1:-1));
}

int main(int argc,char** argv)
{
	
	cin >>n;
	for (i=1;i<=30000;i++)
	{
		f[i]=i;
		len[i]=1;
	}
	for (i=0;i<n;i++)
	{
		cin >>c;
		cin >>p>>q;
		fp=find(p);
		fq=find(q);
		//maxn=max(max(p,q),maxn);
		if ((c=='M')&&(fp!=fq))
		{
			f[fp]=fq;
			dis[fp]+=len[fq];
			len[fq]+=len[fp];
			len[fp]=len[fq];
		}
		else
		{
			if (fp==fq)
				cout <<(abs(dis[p]-dis[q])-1)<<endl;
			else
				cout <<"-1"<<endl;
		}
	}/*测试用 
	for (i=1;i<=maxn;i++)
		cout <<"f["<<i<<"]="<<f[i]<<";dis["<<i<<"]="<<dis[i]<<";len["<<i<<"]="<<len[i]<<endl;
	cout <<f[1]<<" "<<dis[1]<<" "<<len[1]<<endl<<f[30000]<<" "<<dis[30000]<<" "<<len[30000]<<endl;*/
	return 0;
}
2020/8/16 19:53
加载中...