[백준/BOJ] 18116 로봇 조립

문제 : 18116 로봇 조립

18116번: 로봇 조립

서로 다른 부품이 2개가 주어지고 두 부품이

같은 로봇의 부품이란 것을 알려줄 때, 어떤 로봇의

현재까지 알아낸 부품 개수를 출력하면 되는 문제이다.

UnionFind를 사용해 각 부품의 집합을 합쳐주고,

집합을 합칠 때 집합의 크기도 따로 저장해 합쳐주면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, arr[1000005], cnt[1000005];
ll Find(ll x){
    if (x==arr[x])
        return x;
    return arr[x]=Find(arr[x]);
}
void Union(ll x, ll y){
    if (Find(x)!=Find(y)){
        cnt[Find(y)]+=cnt[Find(x)];
        cnt[Find(x)]=0;
        arr[Find(x)]=Find(y);
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i=0;i<1000005;i++){
        arr[i]=i;
        cnt[i]=1;
    }
    while (N--){
        char C;
        ll a, b;
        cin >> C;
        if (C=='I'){
            cin >> a >> b;
            Union(a,b);
        }
        else{
            cin >> a;
            cout << cnt[Find(a)] << "\n";
        }
    }
    return 0;
}