(1765) 닭싸움 팀 정하기

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

단계별로 풀어보기

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

 

 

 

유니온 파인드를 이용해 이분 그래프를 표현할 수 있다. 유니온 파인드 크기를 2N으로 설정해 각 정점 a에 대해 반대 색상을 a+N으로 관리하면 된다. 두 정점 a와 b가 연결되었다면 반대 색상이여야 하므로 a와 b+N, a+N과 b를 같은 집합으로 병합한다.

이때 a와 a+N이 같은 집합이라면 모순이므로 이분 그래프가 아니다.

 

이 문제 자체는 이분 그래프에 대한 문제가 아니지만 같은 방식으로 풀 수 있다. 친구는 항상 같은 팀이여야 하므로 a와 b가 친구라면 a와 b를 병합한다(a+N과 b+N은 병합하면 안 된다). 원수라면 a와 b+N을 병합하고 a+N과 b를 병합한다.

모든 관계를 갱신한 뒤 1~N 중 집합의 개수가 가능한 최대 팀 수이다.

 

 

 

#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, m, ans= 0;
  
  cin >> n >> m;
  
  vector<int> uf(2*n+1);
  
  for(int i=1;i<=2*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--){
    char r;
    int p, q;
    
    cin >> r >> p >> q;
    
    if(r=='F'){
      merge(p, q);
    }else{
      merge(p, q+n);
      merge(q, p+n);
    }
  }
  
  for(int i=1;i<=n;i++){
    ans+= find(find, i)==i;
  }
  
  cout << ans;
  
  return 0;
}