[BOJ 27014] Cube Stacking

https://www.acmicpc.net/problem/27014

27014번: Cube Stacking

Tag : DSU

 

스몰투라지, 세그 등... 뇌절각은 잔뜩 보이는데 

그냥 \(O(logN)\) 이하의 유니온 파인드로 생각을 했을 때 문제되는 부분이 a, b가 직접적으로 부모 자식으로 이어지지 않고

어디 자식으로 갈지 꼬여버려서 단순히 서브트리 크기를 구하는 것은 이 문제에서 각 집합의 루트말고는 제대로 안구해진다는 것인데 경로 압축은 생각하지 말고 \(O(N)\) 유니온 파인드 트리를 생각해보면 어떤 형태여도 조상들에는 불순물 없이

현재 점의 위에 있는 것들이 모두 있다. 조상의 개수를 경로압축할 때 잘 유지되도록 짜면 된다.

 

+ path halving 구현은 쓰지 말자. 다 꼬인다.

+ 그냥 간선 방향을 뒤집어서 아래에 있는것들이 조상들로 고정되게 하면 더 간단하다.

 

구현

#include "bits/stdc++.h"
#define pb push_back
#define endl '\n'

using namespace std;
using ll = long long;
const int di[4] = {0, -1, 0, 1}, dj[4] = {-1, 0, 1, 0};

int n, m;
int pa[30303];
int sz[30303];
int t[30303];

int find(int a) {
    if(pa[a] == a) return a;
    int ret = find(pa[a]);
    t[a] += t[pa[a]];
    pa[a] = ret;
    return ret;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    freopen("input.txt", "r", stdin);

    for(int i = 1; i <= 30000; i++) {
        pa[i] = i;
        sz[i] = 1;
    }
    cin >> m;
    while(m--) {
        char c; cin >> c;
        if(c == 'M') {
            // merge
            int a, b; cin >> a >> b;
            a = find(a); b = find(b);
            if(a != b) {
                t[b] += sz[a];
                sz[a] += sz[b];
                pa[b] = a;
            }
        } else {
            // query
            int x; cin >> x;
            cout << sz[find(x)] - t[x] - 1 << endl;
        }
    }
}