(1717) 집합의 표현

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

단계별로 풀어보기

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

 

 

 

유니온 파인드를 찾으면 항상 따라 나오는 것이 경로 압축 및 랭크 기반 병합이다.

유니온 파인드의 find 함수는 재귀를 이용하기 때문에 데이터가 편향되어 있다면 매우 비효율적으로 작동한다.

그때 사용할 수 있는 최적화 방법이 경로 압축 및 랭크 기반 병합이다.

경로 압축은 재귀를 통해 호출되는 모든 유니온 파인드에 같은 최종 결과를 저장하여 재탐색 효율을 높이는 것이고,

랭크 기반 병합은 집합의 크기나 높이 등을 기반으로 한 랭크를 저장해 병합 과정에서 랭크가 큰 집합에 작은 집합을 병합하여 데이터가 편향되지 않도록 하는 것이다.

일반적으로 최적화를 위해서는 경로 압축만 하면 충분하다.

(랭크 기반 병합을 하면 O(log N)이 O(Ack(N))로 줄어드는데, 어지간한 N의 범위에서는 log N도 충분히 작고 랭크를 저장하기 위한 추가 구현과 메모리가 필요하기 때문)

 

 

 

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

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m;
  
  cin >> n >> m;
  
  vector<int> uf(n+1);
  
  for(int i=1;i<=n;i++)  uf[i]= i;
  
  auto find= [&](auto self, int x) -> int {
    if(uf[x]==x)  return x;
    else  return uf[x]= self(self, uf[x]);
  };
  
  auto merge= [&](int x, int y){
    x= find(find, x);
    y= find(find, y);
    
    uf[y]= x;
  };
  
  while(m--){
    int q, a, b;
    
    cin >> q >> a >> b;
    
    if(!q){
      merge(a, b);
    }else{
      a= find(find, a);
      b= find(find, b);
      
      cout << (a==b ? "YES\n" : "NO\n");
    }
  }
  
  return 0;
}