백준 28277 - 뭉쳐야 산다 (C++)

문제

• 문제 링크

  
   BOJ 28277 - 뭉쳐야 산다 
  

• 문제 요약

$N$개의 집합 $S_1, S_2,$ $...$ $S_N$이 주어질 때, 두 종류로 이루어진 $Q$개의 쿼리를 처리하자.


• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N, Q ≤ 500,000$

$1 ≤ ΣN_i ≤ 500,000$

$1 ≤ S_{i,j} ≤ 1,000,000,000$

알고리즘 분류

• 자료 구조(data_structures)
• 트리를 사용한 집합과 맵(tree _ set / map)
• 작은 집합에서 큰 집합으로 합치는 테크닉(small_to_large)

풀이

$Small$_$To$_$Large$ 테크닉 그 자체인 문제이다.
최근에 만들어진 문제라 솔브수가 적어서 그렇지, 머지 않아 위 테크닉의 대표 예제로 꼽힐 문제일 듯 싶다.

문제로 돌아가서, 우선 $N$개의 집합을 관리해야 함은 필수적이다.
결국 최적화를 시도해 볼 껀덕지는 집합 간 $Merge$가 일어날 때 뿐이다.

단순히 쿼리 그대로 $Merge$를 진행 한다고 해보자.
최악의 경우 큰 집합을 작은 집합으로 매번 복사해주고 있을 테고,
문제를 총 $O(Q * NlogN)$의 시간 복잡도로 풀게 될 것이다.

---

이를 조금만 건드려, 방향이 항상 작은 집합에서 큰 집합으로 향하도록 일반화를 시켜보자.

상대적으로 큰 집합을 $S_i$, 작은 집합을 $S_j$라 하자.

$S_j$의 원소들이 $S_i$로 전이된 후의 결과 $S_{i, j}$가 있을 때,

$2 * Size(S_j) ≤ Size(S_{i, j})$ 가 만족됨을 쉽게 알 수 있다.

결국 크기 차이가 발생하는 집합 간 이동은 $O(logN)$번을 넘을 수 없으므로, 문제를 총 $O(Q * log^2N)$에 근사하게 풀 수 있게된다.

이제 우리는 위를 바탕으로 쉽게 문제를 해결할 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, q; cin >> n >> q;
 
    vector <set<int>> V(n);
    for (auto& S : V)
    {
        int i; cin >> i;
        for (int j; i--; S.insert(j))
            cin >> j;
    }
    for (int o, i, j; q--;)
    {
        cin >> o;
        if (o & 1)
        {
            cin >> i >> j;
            if (V[--i].size() < V[--j].size())
                swap(V[i], V[j]);
 
            for (auto& x : V[j])
                V[i].insert(x);
            V[j].clear();
        }
        else
        {
            cin >> i;
            cout << V[--i].size() << '\n';
        }
    }
}

comment

끝