带权并查集WA
查看原帖
带权并查集WA
930076
mmdxmakioi楼主2023/2/2 19:21
#include<cstdio>
#include<map>
#include<iostream>
#include<string>
using namespace std;
struct node
{
	int fa;
	int rl;
}root[100001];
map<string,int> mp;
string s;
int n,m,q;
void Init()
{
	int i,j;
	for(i=1;i<=n;i++)
	{
		root[i].fa = i;
		root[i].rl = 0;
	}
}
int find(int x)
{
	if(x!=root[x].fa)
	{
		int sv = root[x].fa;
		int sv2 = root[x].rl;
		root[x].fa = find(root[x].fa);
		root[x].rl = (root[sv].rl+sv2)%2;
	}
	return root[x].fa;
}
void merge(int a,int b,int c)
{
	int fa = find(a);
	int fb = find(b);
	root[fa].fa = fb;
	root[fa].rl = (root[a].rl + c)%2;
}
int main()
{
	int i,j;
	cin>>n>>m>>q;
	Init();
	for(i=1;i<=n;i++)
	{
		cin>>s;
		mp[s] = i;
	}
	for(i=1;i<=m;i++)
	{
		int opt;
		string s1,s2;
		cin>>opt>>s1>>s2;
		int x1,x2;
		x1 = mp[s1];
		x2 = mp[s2];
		opt--;
		int fx1,fx2;
		fx1 = find(x1);
		fx2 = find(x2);
		if(fx1==fx2)
		{
			if((root[x1].rl+root[x2].rl)%2==opt)
			{
				printf("YES\n");
			}
			else
			{
				printf("NO\n");
			}
		}
		else
		{
			printf("YES\n");
			merge(x1,x2,opt);
		}
	}
	for(i=1;i<=q;i++)
	{
		string s1,s2;
		cin>>s1>>s2;
		int x1,x2;
		x1 = mp[s1];
		x2 = mp[s2];
		int fx1 = find(x1);
		int fx2 = find(x2);
		if(find(x1)!=find(x2))
		{
			printf("3\n");
		}
		else
		{
			printf("%d\n",(root[x1].rl+root[x2].rl)%2+1);
		}
	}
}

样例过了,显示在CF上#9WA了,思路如下: 同义为00,反义为11,则公式为(x+y)mod2(x+y)\mod 2 ,不知道哪里写挂了

2023/2/2 19:21
加载中...