算法

(带权并查集) $O(t)$

题目大意：现有$30000$个结点，每次给出操作或询问，操作是将某两个结点所在链连接起来，询问是询问在同一个链中的两个结点之间有多少结点。

题解：使用带权并查集，边权存该结点往前到这条链的最前面一共有多少结点，同时最前端的结点上还记录这条链一共有多少结点，路径压缩时直接按照带权并查集的处理方式处理即可，合并集合时除了带权并查集的合并要求外，还要更新现在的顶部结点存的总结点数，用于推出合并时的边权。

C++ 代码

#include <iostream>
#include <cmath>

using namespace std;

const int N = 3e4 + 10;

int p[N], val[N], tot[N]; // tot存的是当前列有多少个节点 

// 并查集核心操作 
int find(int x) {
    if (x == p[x]) return x;
    int new_p = find(p[x]);
    val[x] += val[p[x]]; // 直接累加父亲节点的边权 
    p[x] = new_p; // 路径压缩 
    return new_p;
} 

int main() {
    int t;
    cin >> t;

    // 初始化为前面有0个节点，这条链现在只有自身这一个节点 
    for (int i = 1; i <= 30000; ++i) {
        p[i] = i, val[i] = 0, tot[i] = 1;
    }

    char c;
    for (int i = 1, x, y; i <= t; ++i) {
        if (cin >> c >> x >> y, c == 'M') { // 合并操作 
            val[find(x)] += tot[find(y)];
            tot[p[y]] += tot[p[x]]; //更新新的tot 
            p[p[x]] = p[y]; // 连边 
        }
        else { // 查询 
            if (find(x) == find(y)) { // 如果在同一个链中 
                cout << abs(val[x] - val[y]) - 1 << '\n'; //答案类似于前缀和的方式得出 
            }
            else cout << -1 << '\n';
        }
    }

    return 0;
}