题解：P10734 [NOISG2019 Prelim] Experimental Charges

· · 题解

前置知识：并查集。

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

考虑将每个点加一个对应的虚点，比如 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;
}