关于种族并查集
  • 板块学术版
  • 楼主histcat
  • 当前回复0
  • 已保存回复0
  • 发布时间2022/7/20 11:42
  • 上次更新2023/10/27 19:21:44
查看原帖
关于种族并查集
361592
histcat楼主2022/7/20 11:42
#include<iostream>
#include<cstdlib>
#include<cstdio>


using namespace std;
int n, m;
char opt;
const int N = 2e3 + 10;
int fa[N << 1];

int find(int x)
{
	if(fa[x] == x)
	{
		return x;
	}
	else
	{
		return fa[x] = find(fa[x]);
	}
}

void un(int x, int y)
{
	int t1 = find(x), t2 = find(y);
	if(t1 != t2)
	{
		fa[t2] = t1;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> m;
	
	for(int i = 1;i <= (n << 1);i++)
	{
		fa[i] = i;
	}
	int a, b;
	
	for(int i = 1;i <= m;i++)
	{
		cin >> opt >> a >> b;
		if(opt == 'F')
		{
			un(a, b);
			
		}
		else
		{
			un(a, b + n);
			un(b, a + n);
		}
	}
	int ans = 0;
	for(int i = 1;i <= n;i++)
	{
		if(fa[i] == i)
			ans++;
	}
	cout << ans;
	return 0;
}

此代码如果在if(opt == 'F')大括号中加了一行un(a + n, b + n)就会导致wa,(关于种族并查集了解的不是太深),有dalao能给解释一下吗

Ac代码 Wa代码

2022/7/20 11:42
加载中...