不帶按秩合併的並查集。

維護一下每個點和隊首的距離。

namespace DSU{ // Disjoint Set Union const int N = int(3e4) + 9; int P[N], R[N], prv[N], cnt[N], n; inline void Make(int x){ P[x] = x, R[x] = 0; prv[x] = 0; cnt[x] = 1; } inline int Find(int x){ if (P[x] == x){ return x; } else{ int t = Find(P[x]); prv[x] += prv[P[x]]; P[x] = t; return P[x]; } //return P[x] == x ? x : P[x] = Find(P[x]); } inline void Unionn(int x, int y){ //if (R[x] == R[y]) ++R[x]; //else if (R[x] < R[y]) swap(x, y); P[y] = x; prv[y] += cnt[x]; cnt[x] += cnt[y]; } inline void Union(int x, int y){ x = Find(x), y = Find(y), Unionn(x, y); } inline void Init(){ REP_1(i, n) Make(i); } } using namespace DSU; int main(){ #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif n = int(3e4); Init(); Rush{ char cmd; RC(cmd); int x, y; RD(x, y); if (cmd == 'M'){ //cout << x << " " << y << endl; Union(y, x); } else{ //cout << Find(x) << " " << Find(y) << endl; if (Find(x) != Find(y)) puts("-1"); else{ printf("%d\n", abs(prv[x] - prv[y]) - 1); } } } }