这是经典并查集题目:

把每个电荷拆成两个结点 i,ii,i'

  • A x y 时连边 xyx \leftrightarrow yxyx' \leftrightarrow y'
  • A x y 时连边 xyx \leftrightarrow y'xyx' \leftrightarrow y
  • Q x y 时:
    • xxyy 连通就输出 A
    • xxyy' 连通就输出 R
    • 都不连通就输出 ?
#include <bits/stdc++.h>
using namespace std;
int ld[1000012], co[1000012], sz[1000012];
void init(int n)
{
	for (int i = 1; i <= n; i++)
		ld[i] = i, co[i] = 0, sz[i] = 1;
}
pair<int, int> want(int x)
{
	stack<pair<int, int> > s;
	s.push(make_pair(x, 0));
	int tc = 0, y = x;
	while (ld[x] != x)
	{
		tc += co[x];
		x = ld[x];
		s.push(make_pair(x, tc));
	}
	while (!s.empty())
	{
		pair<int, int> u = s.top();
		s.pop();
		ld[u.first] = x;
		co[u.first] = tc - u.second;
	}
	return make_pair(ld[y], co[y]);
}
void add(int x, int y, int c)
{
	x = want(x).first, y = want(y).first;
	if (x == y) return;
	ld[y] = x, co[y] = c, sz[x] += sz[y], sz[y] = 0;
}
bool tg(int x, int y)
{
	pair<int, int> xx = want(x), yy = want(y);
	return (xx.first == yy.first);
}
int dis(int x, int y)
{
	pair<int, int> xx = want(x), yy = want(y);
	return xx.second - yy.second;
}
int main()
{
	int n, m;
	cin >> n >> m;
	init(2 * n);
    while (m--)
    {
        char c;
        int x, y;
        cin >> c >> x >> y;
        if (c == 'A') add(x, y + n, 0), add(x + n, y, 0);
        if (c == 'R') add(x, y, 0), add(x + n, y + n, 0);
        if (c == 'Q')
        {
            if (tg(x, y + n)) puts("A");
            else if (tg(x, y)) puts("R");
            else puts("?");
        }
    }
	return 0;
}