(28277) 뭉쳐야 산다

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

단계별로 풀어보기

43단계(유니온 파인드 2) 1번째

 

 

 

유니온 파인드는 아니고 Small to Large Trick에 대해 알아보는 문제.

집합을 서로 합치는 연산을 할 때 최적화하는 기법이다. N개의 크기 1인 disjoint한 집합을 합치는 연산을 한다고 생각하자. A집합에 B집합을 합치는 연산은 B의 원소 크기에 비례하므로 O(|B|)이다. 이때 항상 작은 집합 B를 큰 집합 A에 합친다고 가정하면 2*|B|≤|A∪B|이므로 항상 원소의 개수가 2배 이상 커지는 집합으로 옮겨가게 된다. 어떤 집합의 원소의 개수의 최댓값은 N개이므로 각 원소는 이동하는 연산을 O(log N)번 이상 수행하지 않으므로 모든 집합을 합쳤을 때 시간복잡도는 O(N log N)이 된다.

만약 집합끼리 disjoint하지 않다고 해도 성립한다. 이 경우 A에만 존재하는 |A-A∩B|개의 원소만 이동 연산을 수행하고 나머지 |A∩B|개의 원소는 이미 B에 있으므로 O(1)의 삭제 연산을 수행한 것이나 마찬가지다. 따라서 A-A∩B 집합과 합치는 연산을 했다고 볼 수 있고, 이는 disjoint하므로 위의 증명이 성립한다.

 

이 문제에서 모든 집합의 원소의 총합은 50만이므로 Small to Large Trick을 쓰면 집합을 합치는 과정을 O(N log N)으로 시간 내에 해낼 수 있다.

 

 

 

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, q;
  
  cin >> n >> q;
  
  vector<set<int>> v(n+1);
  
  for(int i=1;i<=n;i++){
    int sz;
    
    cin >> sz;
    
    vector<int> tmp(sz);
    
    for(int j=0;j<sz;j++)  cin >> tmp[j];
    
    v[i].insert(tmp.begin(), tmp.end());
  }
  
  while(q--){
    int c;
    
    cin >> c;
    
    if(c==1){
      int a, b;
      
      cin >> a >> b;
      
      if(v[a].size()<v[b].size()) swap(v[a],v[b]);
      
      v[a].insert(v[b].begin(), v[b].end());
      v[b].clear();
    }else{
      int a;
      
      cin >> a;
      
      cout << v[a].size() << "\n";
    }
  }
  
  return 0;
}