- P118's solution
-
题解 P118
- @ 2025-12-3 18:10:58
按题意直接模拟即可。(代码里都有注释)
AC code:
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int parent[MAXN];
int rank_[MAXN];
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]); // 路径压缩
}
return parent[x];
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
// 按秩合并
if (rank_[x] < rank_[y]) {
parent[x] = y;
} else {
parent[y] = x;
if (rank_[x] == rank_[y]) {
rank_[x]++;
}
}
}
int main() {
int N, Q;
scanf("%d %d", &N, &Q);
// 初始化并查集:节点 1~N 表示正电荷,N+1~2N 表示负电荷
for (int i = 1; i <= 2 * N; i++) {
parent[i] = i;
rank_[i] = 0;
}
while (Q--) {
char op[2];
int a, b;
scanf("%s %d %d", op, &a, &b);
if (op[0] == 'A') {
// A操作:a 和 b 互相吸引,合并 a 与 b+N,a+N 与 b
unite(a, b + N);
unite(a + N, b);
} else if (op[0] == 'R') {
// R 操作:a 和 b 互相排斥,合并 a 与 b,a+N 与 b+N
unite(a, b);
unite(a + N, b + N);
} else if (op[0] == 'Q') {
// Q 操作:查询 a 和 b 的关系
if (find(a) == find(b)) {
printf("R\n"); // 同一集合,排斥
} else if (find(a) == find(b + N)) {
printf("A\n"); // a 的正电荷与 b 的负电荷同一集合,吸引
} else {
printf("?\n"); // 无法确定
}
}
}
return 0;
}