蒟蒻求助,并查集!
查看原帖
蒟蒻求助,并查集!
637526
James_kttt楼主2023/1/20 10:53

下面是代码,请各位大佬帮忙看看,除了第一个测试点过了,其他全部WA

//James_Kttt
#include <iostream>
#include <cstdio>
using namespace std;

int t, fuc[300005], num[300005], fa[300005], a, b;
char f;

int FindFather(int k)
{
	if(fuc[k] == k)
		return k;
	else
	{
		int NOW = fuc[k];
		fuc[k] = FindFather(fuc[k]);
		num[k]+=num[NOW]-1;
		return fuc[k];
	}
}

void Together(int x,int y)
{
	num[FindFather(x)] = fa[FindFather(y)] + 1;   
	fa[FindFather(x)] += fa[FindFather(x)];
	fuc[FindFather(x)] = FindFather(y);
}

void Begain(int ans)
{
	for(int i = 1;i<=ans;i++)
	{
		fuc[i] = i;
		num[i] = 1;
		fa[i] = 1;
	}
}

int main()
{
	cin>>t;
	Begain(30005);
	for(int i = 1;i<=t;i++)
	{
		cin>>f>>a>>b;
		if(f == 'M')
			Together(a,b);
		else
		{
			if(FindFather(a)!=FindFather(b))
				cout<<"-1"<<endl;
			else
				cout<<abs(num[a]-num[b])-1<<endl;
		}
	}
	return 0;
}
2023/1/20 10:53
加载中...