自动搬运

查看原文

来自洛谷，原作者为

	wcy110614 lichess : wangcy 笨蛋。

搬运于2025-08-24 23:00:46，当前版本为作者最后更新于2024-07-10 15:52:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前置知识：并查集。

虽然这道题并不算太难，但是没见过这个套路还是有难度的。

考虑将每个点加一个对应的虚点，比如 $A\rightarrow A'$ 表示 $A'$ 的所带的电荷和 $A$ 相反。

1. 如果 $A,B$ 互相吸引，那么 $A,B$ 所对应的集合相反，则 $A - B',B-A'$ 连边。

2. 如果 $A,B$ 互相排斥，说明 $A,B$ 所在的集合相同，则 $A - B,A'-B'$ 连边。

3. 分类讨论判断 $A,B$ 所在的集合。如果 $A,B$ 之间有边，$A,B$ 就会有相同电荷，排斥。如果 $A,B'$ 之间有边，$A,B$ 就会有不同电荷，吸引。如果这两条边都没有，那就完全得不到任何关系，这个时候输出 ?。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n,m,f[N];
int gf(int x){return x==f[x]?f[x]:f[x]=gf(f[x]);}
void link(int x,int y){
	int u=gf(x),v=gf(y);
	f[u]=v;
}
int main(){
	for(int i=1;i<N;++i)f[i]=i;
	cin>>n>>m;
	while(m--){
		char op;int a,b;
		cin>>op>>a>>b;
		if(op=='A')link(a,b+n),link(a+n,b);
		else if(op=='R')link(a,b),link(a+n,b+n);
		else{
			int fl=0;
			if(gf(a)==gf(b)||gf(a+n)==gf(b+n))cout<<'R';
			else if(gf(a+n)==gf(b)||gf(a)==gf(b+n))cout<<'A';
			else cout<<'?';
			cout<<"\n";
		}
	}
	return 0;
}