유니온파인드에서 집합 내 원소 다른 집합으로 이동시키기

Union-find 다른 말로 Disjoint sets(상호 배타적 집합) 이란 여러개의 집합들에 대해,

서로 다른 두 집합의 교집합이 공집합이며, 모든 집합들의 합집합이 전체 집합이 되는 집합들을 말한다.

그런데 이게 유용한 이유는 이렇다.

1. 서로 다른 두 원소가 같은 집합 내에 속해 있는지, 아니면 서로 다른 집합에 속해있는 지를 빠른 시간내에 구할 수가 있다.

2. 서로 다른 집합에 속해있는 두 노드가 속해있는 두 집합을 빠른시간에 합쳐 더 큰 하나의 집합으로 만들 수가 있다.

그렇기 때문에 크루스칼 알고리즘에서도 유용하며, dfs 대용으로도 쓸 수가 있으며 그 활용이 무궁무진하다.

그런데 일반적인 방법으로는 집합을 한꺼번에 합치는 것은 가능하지만, 집합 내의 특정 한 원소 단위로는

옮길 수가 없다. 하지만 약간의 트릭을 통해 이것을 가능하게 할 수가 있다.

일반적인 유니온파인드에서 트리의 중간에 있는 어떤 노드 A를 다른 집합으로 옮긴다고 가정해보자.

그럼 단순히 A의 부모만 다른집합의 루트노드로 바꿔준다고 해서 끝날 문제가 아니다. 왜냐하면

A의 자식들이 존재할 수가 있기 때문이다. 만약 단순히 A의 부모만 바꾸어 준다면, 

A만 다른 집합으로 옮기는 것이 아니라 A의 자식들 도 같이 다른 집합으로 옮겨 버린다.

게다가 이 A의 자식들은 누가될지 모른다. A와 같은 집합 내에 포함되어 있는 임의의 원소들이라는 것만 알뿐이다.

그렇다면 이 문제를 어떻게 해결할 수 있을까? 현재 우리의 문제는 옮기려는 원소가 트리 상에서 자식을 가지고있기

때문이다. 그러면 자식을 가지지 않도록 해주면 되지않을까? 어떻게 자식을 가지지 않게 할까?

A노드에 자식 B가 있다는 것은 자식B와 A를 merge 해줬었다는 것이 된다. 그러면 애초에 merge 를 해줄 때

A와 B가 부모-자식 관계를 이루지 않으면서 같은 집합에 있다고 표시해줄 방법만 찾으면 이 문제는 해결될 것이다.

여기가 중요하다. A와 B가 부모-자식 관계를 이루지 않게 하기위해 우리는 맨처음에 각 집합당 하나씩

가상의 관리자 노드를 미리 만들어 준다. 관리자는 집합내 모든 원소들을 동등하게 보고 직접 관리한다.

merge 를 할 때는 이 관리자들 끼리 붙이고 둘 중에서 다시 대표 관리자를 한명 고른다.

migration 할 때는 옮기려는 노드만 똑 떼서 넣고 싶은 집합의 관리자에 톡 붙여준다. 그러면 절대로 실제 노드(원소)끼리는

부모 자식 관계를 이루지 않기 때문에 특정 원소를 다른 집합으로 옮길 때에 신경써줘야할 게 전혀 없다.

이렇게 하면 초기 상태와 연산 중간의 모양은 이런 꼴이된다.

초기에 노드가 6개(집합이 6개) 이고 

merge 3 4 

migrate 5 6

을 하고난 후의 모습이 위의 사진이다. 검은 노드가 관리자 노드, 숫자가 적혀있는 노드가 실제노드.

아래는 수 많은 merge와 migrate 연산후의 모습의 예이다.

관리자 노드는 합과 크기가 모두 0이기 때문에 merge 를 해도 전혀 계산에 고려되지 않기 때문에 

집합의 원소의 수나 원소번호의 합을 구할 때는 없는 것처럼 보인다. 하지만 실제로 merge를 할 때에는

관리자 단위로 붙기 때문에 중간 중간에 관리자 노드들이 많이 있고, 그래서 모든 실제 원소들이 다른 원소를 거치지 않고도

대표(조상)노드까지 갈 수 있게 한다. 이것은 모든 실제 원소들이 자식을 가지지 않는 말과 동치이다.

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
 
int N,M;
int par[200003];
int size[200003];
long long sum[200003];
 
int op,a,b,c;
 
// find 와 merge는 일반적인 union-find와 완전히 똑같다.
int find(int u){
    return par[u] == u ? u : par[u] = find(par[u]);
}
void merge(int u, int v){
    u = find(u), v = find(v);
    if(u == v) return;
    par[u] = v;
    size[v] += size[u];
    sum[v] += sum[u];
}
void migrate(int u, int v){
    int ur = find(u);
    int vr = find(v);
    size[ur]--;
    sum[ur]-=u;
    size[vr]++;
    sum[vr]+=u;
    par[u] = vr; // 옮기려는 노드 하나만 똑 떼어 옮기려는 집합에 직접 톡 붙인다.
}
int main() {
    while(scanf("%d%d",&N, &M) != -1){
        for(int i = 1 ; i <= N; i++) {
            par[i] = i+N, size[i] = 1, sum[i] = i; // 맨처음에 각 집합(원소 i)의 관리자 노드는 i+N로 준다.
            par[i+N] = i+N, size[i+N] = size[i], sum[i+N] = sum[i]; // 관리자 노드의 크기와 번호는 0으로 보고 계산.
        }
        for(int i = 0 ; i < M; i++) {
            scanf("%d",&op);
            if(op == 1){
                scanf("%d%d",&a,&b);
                merge(a,b);
            }
            else if(op == 2){
                scanf("%d%d",&a,&b);
                migrate(a,b);
            }
            else if(op == 3){
                scanf("%d",&a);
                a = find(a);
                printf("%d %lld\n", size[a], sum[a]);
            }
        }
    }        
    return 0;
}