(28121) 산책과 쿼리

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

단계별로 풀어보기

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

 

 

 

어떤 산책로를 왔다갔다 하면 짝수 시간 산책은 가능하다. 하지만 홀수인 시간을 하려면 길이가 홀수인 사이클이 존재해야 한다(정점의 수는 30만 이하로 가장 긴 사이클도 100만으로 주어진 최소 만족스러운 시간 산책보다 짧으므로 홀수이기만 하면 된다).

다시 말해 매 쿼리마다 이분 그래프로 표현이 불가능한 정점의 수를 구하는 문제다.

이분 그래프를 유니온 파인드로 관리하는 법은 이전 문제에서 설명했으며, a와 a+N이 같은 집합이라면 이분 그래프가 될 수 없으므로 a가 속한 집합의 정점만큼 더해줘야 한다. 여기서 보다시피 크기도 관리하는 유니온 파인드를 선언해야 한다.

주의할 점으로 이분 그래프가 아닌 집합은 어떤 정점과 반대 색 정점이 전부 같은 집합이므로 집합의 크기를 2로 나눠줘야 한다.

반대로 이분 그래프 집합은 크기가 2배가 아니기 때문에 이분 그래프가 아닌 집합과 맞는 집합을 병합하는 경우 이분 그래프가 아닌 집합을 빼준 뒤 병합하고 다시 더해줘야 한다.

 

 

 

#include <iostream>
#include <vector>
using namespace std;
typedef pair<int,int> p;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, q, res= 0;
  
  cin >> n >> q;
  
  vector<p> uf(2*n+1);
  
  for(int i=1;i<=2*n;i++)  uf[i]= {i,1};
  
  auto find= [&](auto self, int x) -> p {
    if(uf[x].first==x)  return uf[x];
    else  return uf[x]= self(self, uf[x].first);
  };
  
  auto merge= [&](int x, int y){
    p xres= find(find, x);
    p yres= find(find, y);
    
    if(xres.first==yres.first)  return;
    
    uf[xres.first].second+= uf[yres.first].second;
    uf[yres.first].first= xres.first;
  };
  
  auto isvaild= [&](int x){
    return find(find, x)!=find(find, x+n);
  };
  
  while(q--){
    int a, b;
    
    cin >> a >> b;
    
    if(isvaild(a)&&isvaild(b)){
      merge(a, b+n);
      merge(b, a+n);
      
      if(!isvaild(a))  res+= find(find, a).second;
    }else if(isvaild(a)){
      res-= find(find, b).second;
      
      merge(a, b+n);
      merge(b, a+n);
      
      res+= find(find, b).second;
    }else if(isvaild(b)){
      res-= find(find, a).second;
      
      merge(a, b+n);
      merge(b, a+n);
      
      res+= find(find, a).second;
    }
    
    cout << res/2 << "\n";
  }
  
  return 0;
}