某岛

… : "…アッカリ~ン . .. . " .. .
March 20, 2020

Vijos 1443. 银河英雄传

Vijos 传送门

不带按秩合并的并查集。
维护一下每个点和队首的距离。

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);
            }
        }
    }
}