분리집합이라고도 불리는 유니온파인드에 대해 알아보겠습니다.
유니온파인드는 각 원소를 함께 묶을 수 있습니다.
뼈대 생성
vector<int> u(len);
for(int i = 0; i < len; i++) {
u[i] = i;
}u라는 벡터를 만들어서 분리집합을 구현합니다.
벡터의 값은 소속된 집합을 나타냅니다.
벡터의 값을 인덱스와 동일하게 맞춰주어 초기화합니다.
현재 상태에서 모든 원소는 서로 연결되어있지 않은 상태입니다.
ufind
int ufind(int& k) {
int& ret = u[k];
if(ret == k) return k;
ret = ufind(ret);
return ret;
}ufind함수는 원소가 소속된 집합의 번호를 반환합니다.
u[k] = k 가 될때까지 재귀적으로 반복합니다.
연결확인
int A = ufind(a);
int B = ufind(b);
if(A == B) {
// connected
}ufind 결과가 서로 동일하다면 같은 집합에 소속되어 연결되어 있음을 알 수 있습니다.
연결하기
u[ufind(a)] = ufind(b);위와 같은 코드를 이용하여, 원소를 연결해줄 수 있습니다.
