一、问题背景
题目模拟了银河战舰的队列管理，需要处理两种操作：合并战舰队列和查询战舰间距离。这是一个典型的并查集应用问题，但需要额外维护距离信息。
二、完整代码解析（含详细注释）
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const int MAXN = 30010; // 最大战舰数量
// 三个核心数组：
int parent[MAXN]; // 记录每个战舰的父节点
int dist[MAXN]; // 记录每个战舰到父节点的距离
int size[MAXN]; // 记录每个集合的大小(队列长度)
// 初始化并查集
void init() {
for (int i = 1; i < MAXN; i++) {
parent[i] = i; // 初始时每个战舰自成一队
dist[i] = 0; // 到自己的距离为0
size[i] = 1; // 队列大小为1
}
}
// 查找根节点，同时路径压缩并更新距离
int find(int x) {
if (parent[x] != x) {
int root = find(parent[x]); // 递归找根
dist[x] += dist[parent[x]]; // 关键：累加距离(路径压缩时维护距离)
parent[x] = root; // 路径压缩
}
return parent[x];
}
// 合并两个集合(将x所在队列接到y所在队列末尾)
void merge(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
parent[rootX] = rootY; // 将x的根节点连接到y的根节点
dist[rootX] = size[rootY]; // x根节点到新根的距离是y队列原长度
size[rootY] += size[rootX]; // 更新新队列的总长度
}
}
int main() {
ios::sync_with_stdio(false); // 加速输入输出
cin.tie(nullptr);
init(); // 初始化并查集
int T; // 指令数量
cin >> T;
while (T--) {
char op; // 指令类型
int i, j;
cin >> op >> i >> j;
if (op == 'M') {
merge(i, j); // 合并指令
} else {
// 查询指令
int rootI = find(i);
int rootJ = find(j);
if (rootI != rootJ) {
cout << -1 << "\n"; // 不在同一队列
} else {
// 计算两战舰间隔的战舰数
int ans = abs(dist[i] - dist[j]) - 1;
cout << (ans < 0 ? 0 : ans) << "\n"; // 处理相邻情况
}
}
}
return 0;
}
