UnionFind問題の基本(C++)

## Union-Find問題とは
誤解を恐れずに大まかに説明すると，集合操作union, findからなる命令列$σ$を初期状態 $S_1 = \\{1\\}, S_2 = \\{2\\}, ... , S_n = \\{n\\}$から実行するような問題．
$S_i$ は木構造で管理することが多い．

#### 集合の操作 union と find
union($S_i$, $S_j$) : $S_i$ $=$ $S_i$ $\cup$ $S_j$ とし， $S_j$を削除する操作．
find($a$) : $a$ $\in$ $S_i$ である$i \in \\{1, 2, ... , n\\}$を返す操作．

## C++での実装
構造体UnionFindを定義．
```C++
struct UnionFind{
    vector<int> S; //各ノードiが含まれる木構造のルートを格納する配列：iがルートの場合負の値
    
    /*コンストラクタ*/
    UnionFind(){}
    UnionFind(int n) : S(n, -1) {}

    /*find(a)の実装*/
    int root(int v){
        if(S.at(v) < 0)
            return v; 
        else
            return S.at(v) = root(S.at(v));
        }

    /*union(Si, Sj)の実装*/
    void merge(int x, int y){
        int x_root = root(x);
        int y_root = root(y);

        if(x_root == y_root)
            return;
        else if(S.at(x_root) > S.at(y_root))
            swap(x_root, y_root);

        S.at(x_root) += S.at(y_root);
        S.at(y_root) = x_root;
        return;
        }
    };
```
### ソースコードの解説
筆者自身の復習もかねてなるべく丁寧にソースコードを追っていきたいと思います．

#### メンバ変数・コンストラクタ
まず，構造体UnionFindのメンバとしてint型の配列を用意しています．

`UnionFind S(n);`のようにUnionFind型のオブジェクトが生成された際には，
$$ S = \\{-1, -1, ... , -1\\}$$
というように配列の要素がすべて-1で初期化されます．

#### root関数
root関数はunion, findのfind操作に該当する操作を行う関数です．
具体例を使って説明していきます．
初期状態，すなわち配列要素がすべて-1の場合，root(0)はどのように動作するでしょうか？

S.at(0) = -1 < 0 であるため root関数の返り値として 0 が返ってくることがわかります．
これはつまり，S.at(v) < 0 である場合，その v 自身がルートであるということです．

S.at(v) < 0 でない場合の挙動についての説明はmerge関数の解説と合わせた方が理解しやすいと思うので次にmerge関数について解説します．

#### merge関数
merge関数はunion, findのunion操作に該当する操作を行う関数です．
merge関数は2つの引数を(x, y)受け取り，まずノード x とノード y のルートを計算します．
ルートが等しい場合は x と y は同じ木構造に含まれているということなのでunion操作は必要ありません．

初期状態から union(0, 1) を実行する流れは次の通りです．
1. root(0) = 0, root(1) = 1 より，merge が必要です．
2. S.at(0) = -1, S.at(1) = -1 より，else if部分は飛ばされます（else if部分についてはすぐに解説します）
3. S.at(0) += S.at(1) より S.at(0) = -2 へ更新．
4. S.at(1) = 0 へ更新．

else if の部分について解説します．
S.at(x_root) > S.at(y_root) の際に x_root と y_root の値を入れ替えることで，merge 操作後の木の高さがより低くなるようにしています．文字だけだと分かりにくいと思うので，図を用いて説明します．
次の2つの部分木の merge を考えます．
左の部分木 は merge(0, 2)とすることで得られます．
このとき，$S = \\{-2, -1, 0, -1, -1, -1\\}$
```mermaid
flowchart TD
    node((0));
    node1((1));
    node --- node2((2));
```
0 がルートとなる場合，次のようになります．
```mermaid
flowchart TD
    node((0));
    node1((1));
    node --- node2((2));
    node --- node1;
```
1 がルートとなる場合，次のようになります．
```mermaid
flowchart TD
    node((0));
    node1((1));
    node --- node2((2));
    node1 --- node;
```
merge 後の2つの部分木を比べるとそれぞれ木の高さが 2, 3となっており前者の方が木の高さが低くなっていることがわかります．
このことから，else if以降の操作を行っているという訳です．
#### root関数その2
先ほど飛ばした S.at(v) < 0 でない場合について解説します．
merge(0, 1), merge(2, 3)実行後に merge(1, 3)を実行することを考えます．
merge(0, 1), merge(2, 3)を実行後の部分木および配列は次のようになっています．
```mermaid
flowchart TD
    node((0));
    node1((1));
    node2((2));
    node3((3));
    node --- node1;
    node2 --- node3;
```
$ S = \\{-2, 0, -2, 2\\}$

merge(1, 3)を実行します．
1. root(1) = root(0) = 0, root(3) = root(2) = 2
2. S.at(0) += S.at(2)
2. S.at(2) = 0

すなわち，以下のような部分木および配列となっています．
```mermaid
flowchart TD
    node((0));
    node1((1));
    node2((2));
    node3((3));
    node --- node1;
    node2 --- node3;
    node --- node2;
```
$S = \\{-4, 0, 0, 2\\}$
ここで，root(3)を呼び出してみましょう．
1. S.at(3) = 2 >= 0 よりelse以降へ
1. S.at(3) = root(S.at(3)) = root(2)
1. root(2) = 0 >=0 よりelse以降へ
1. S.at(2) = root(S.at(2)) = root(0)
1. S.at(0) = -4 < 0 より return 0
1. root(0) = 0 より root(2) = 0
1. root(2) = 0 より S.at(3) = 0

すなわち配列としては，
$S = \\{-4, 0, 0, 0\\}$
となります．
これは部分木としては，
```mermaid
flowchart TD
    node((0));
    node1((1));
    node2((2));
    node3((3));
    node --- node1;
    node --- node2;
    node --- node3;
```
となっており，merge(1, 3) 実行後の部分木よりも高さが低くなっています．
こうすることで，次に root(3) を実行する時に7ステップも計算に費やさなくてもよくなります．

以上がUnionFind問題のためのデータ構造とアルゴリズムになります．

### まとめ
UnionFind問題は union 操作と find 操作を初期状態から適用していく問題．
merge 操作の際にすでに頂点が2以上の部分木の方へ部分木を付け加えることで木の高さを抑えられる．
root 操作では部分木の再構成も行っている．
復習用の備忘録ですが，少しでも参考になれば幸いです．

感想：コードだとS.at(v) = root(S.at(v))だけなのに，部分木の再構成という計算量短縮のための工夫が濃縮されていて感動しました．