(13306) 트리

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

단계별로 풀어보기

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

 

 

 

유니온 파인드는 아니고 오프라인 쿼리에 대해 배우는 문제.

주어지는 쿼리를 들어오는 순서대로 처리하지 않는 것이 포인트인데, 일단 쿼리를 전부 저장한 뒤 원하는(주로 계산에 유리한) 순서대로 수행해 일괄적으로 답을 내는 기법을 의미한다.

이 문제에서 주어지는 집합을 쪼개는 연산은 배운 적 없지만 이 쿼리를 전부 거꾸로 수행한다고 생각하면 쪼개진 집합을 다시 붙이는 연산이 되고, 이것은 유니온 파인드로 해결 가능하다. 답을 거꾸로 수행하며 구했으므로 당연히 출력할 때 다시 뒤집어줘야 한다.

 

 

 

#include <iostream>
#include <vector>
#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<int> uf(n+1), parent(n+1);
  vector<pair<int,int>> query(n+q-1);
  vector<bool> ans;
  
  for(int i=2;i<=n;i++)  cin >> parent[i];
  
  for(int i=0;i<n+q-1;i++){
    int qtype;
    
    cin >> qtype;
    
    if(qtype==0)  cin >> query[i].second;
    else  cin >> query[i].first >> query[i].second;
  }
  
  reverse(query.begin(), query.end());
  
  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;
  };
  
  for(auto now:query){
    if(now.first==0){
      merge(now.second, parent[now.second]);
    }else{
      ans.push_back(find(find, now.first)==find(find, now.second));
    }
  }
  
  reverse(ans.begin(), ans.end());
  
  for(bool res:ans)  cout << (res?"YES\n":"NO\n");
  
  return 0;
}