Union-Findのデータ構造【競技プログラミング】

# はじめに
- 最近、[データ構造づいていた(スタック、キュー、ヒープ)](https://qiita.com/kei_tnk/items/47f952f3053301faa265)けど、今回は[Union-Find](https://ja.wikipedia.org/wiki/%E7%B4%A0%E9%9B%86%E5%90%88%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0)をswiftに導入してみる。
- ヒープは、溜め込んだデータの内、最大（最小）のデータを取り出す計算量がO(1)と極めて小さく、データを溜め込むときの計算量もO(logN)と比較的小さかった。
- Union-Findの特徴は、非常に小さい計算量で、データを「グループ分け」する事が出来ること。
- まず、初期化時点で全てのデータ(n個の場合、0..<nのインデックスが付された要素)が存在し、データの追加や削除はされない。メソッドは、unite(同じグループにする)とisSame(同じグループかどうか判定する)の2つのみ。統合（unite）は出来るが、分離は出来ない。また、同じグループかどうかが分かるだけであり、グループ名は得られない。

# Union-Findの考え方
- uniteとisSameを少ない計算量で実現するのが、Union-Find木であるが、なぜ、treeだと、少ない計算量で計算できるのかは、下記のAtCoderのスライドを見て欲しい。p5のように、配列を使って、「同じ数字なら同じグループ」のようなアルゴリズムだと、2つの要素をuniteしたとき、片方のグループに割り当てた数字を全て塗り返さなくてはならず、O(n)の計算量が必要となり、無駄に計算量を喰ってしまう。
<iframe src="//www.slideshare.net/slideshow/embed_code/key/CIWAduFPvzGrrE" width="595" height="485" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe>

- これにたいし、p7のようにtree構造を考え、p9のように「根が同じであれば、同じグループである」とすれば、uniteの計算量は小さくできる。

# Union-Find木を使った実装化
- c++用のスライドのコードをswiftで実装する
```swift
struct UnionFind {
    
    private var par:[Int] = [] // treeの親ノードを格納する。
    
    init(_ n:Int) {
        for i in 0..<n {par.append(i)} 
    }
    
    mutating func root(_ i:Int)->Int {
        if par[i] == i {return i} // 自身が根なら自身を返す
        par[i] = root(par[i])  // 再帰計算の途中で経路圧縮もついでに行う。
        return par[i]        // 再帰計算で値を返す
    }
    
    mutating func unite(_ i:Int,_ j:Int){
        let (ri,rj) = (root(i),root(j))
        if ri == rj {return} // 根が同じなら何もしない
        par[ri] = rj       // ri(iの根)の根をrjとする
    }
    
    mutating func isSame(_ i:Int,_ j:Int)->Bool { root(i) == root(j) }
}

var uf = UnionFind(10)
print(uf.isSame(0,9)) // false
uf.unite(0,5) // 0と5が同じグループ
print(uf.isSame(0,9)) // false
uf.unite(5,9) // 5と9が同じグループ
print(uf.isSame(0,9)) // true -- 0と9が同じグループ
```

# 高機能化
- 前記のコードで、配列par[i]は、番号iの親ノードの番号を格納していた。
- 当然、番号iが最上位の親ノード（根）であれば、par[i]には、iが格納される。
- だけど、根の要素に根の番号が格納されているのはMOTTAINAI!と、地球上の誰かがふと思った。…地球上の誰かがふと思ったのだ…配列（みんな）の未来を守らねばと…
- そんなわけで、iが根であるとき、par[i]を負数とし、その負数の絶対値は根に属するノードの数とすることにします。つまり、根の要素の値を見ることで、そのグループに属する数が分かることになります。
- この思想で前記のコードを書き換える。まず、配列parの初期値は全て「-1」となる。つまり、全ての要素が根(負数)であり、その根に属するノード数は根自身のみの1(負数の絶対値)となる。
```swift
struct UnionFind {
    
    private var par:[Int] = [] // treeの親ノードを格納する。
    var parent:[Int] { par }
    
    init(_ n:Int) {
        par = [Int](repeating:-1,count:n)
    }
    
    mutating func root(_ i:Int)->Int {
        if par[i] < 0 {return i} // 自身が根なら自身を返す
        par[i] = root(par[i])  // 再帰計算の途中で経路圧縮もついでに行う。
        return par[i]        // 再帰計算で値を返す
    }
    
    mutating func unite(_ i:Int,_ j:Int){
        let (ri,rj) = (root(i),root(j))
        if ri == rj {return} // 根が同じなら何もしない
        
        // riの根をrjとする。
        par[rj] += par[ri] // 根rjの仲間の数に、riの仲間の数を加える
        par[ri] = rj       // ri(iの根)の根をrjとする
    }
    
    mutating func isSame(_ i:Int,_ j:Int)->Bool { root(i) == root(j) }
}
```
```swift
// 入力
var uf = UnionFind(10)
uf.unite(0,5) // 0と5が同じグループ
uf.unite(5,9) // 5と9が同じグループ
uf.unite(2,3) // 2と3が同じグループ
uf.unite(2,4) // 2と4が同じグループ

for i in 0..<10 {
    print(i,uf.parent[i],uf.root(i)) //ノード番号、親番号、根番号
}

// 出力
0 5 9 //ノード0の親は5で、根は9
1 -1 1
2 3 4
3 4 4
4 -3 4
5 9 9 //ノード5の親は9で、根は9
6 -1 6
7 -1 7
8 -1 8
9 -3 9 //ノード9は根で、仲間は3つ
```

# 実装したUnion-Findの活用方法
- グループ化が高速で実行できたとして、何が嬉しいの？
- というのが普通の感想だと思うので、活用例を示そうと思う。
- とは言え、活用例も[AtCoderの問題](https://atcoder.jp/contests/abc177/tasks/abc177_d)を解くことだから、「活用方法」と呼ぶのは恥ずかしいかも。
![スクリーンショット 2024-08-01 22.45.07.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2733720/13c94aff-b3b1-7a30-dacc-1f90ee79ae6f.jpeg)
- 上記の問題は、最大のお友達集団の人数を調べることが回答に繋がる。最大のお友達集団の全員を別々のグループに分けるための最小のグループ数は、当然、最大のお友達集団の人数と一致する。
- 入力値
```
10 4 //ノード数10、お友達ペア4
3 1 //ペア① 3と1は友達
4 1 //ペア② 4と1は友達
5 9 //ペア③ 5と9は友達
2 6 //ペア④ 2と6は友達
```
- 回答用コード
```swift
let (N,M) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0],$0[1])}[0]

var uf = UnionFind(N)

for _ in 0..<M {
    // 問題文のノード番号から1を引いて、配列のindexにする。
    let (a,b) = [readLine()!.split(separator:" ").map{Int($0)!}].map{($0[0]-1,$0[1]-1)}[0] 
    uf.unite(a,b)
}

var ans = 0
for i in 0..<N {
    ans = max(ans,-uf.parent[i])
}

print(ans)
```

# さいごに
- 活用例で示したAtCoderの問題は、Union-Findを知っていれば、すごく簡単な問題に思えるけど、ABCコンテストが6問だった時代のd問題なんだよね。だから、実は難易度高めの問題。
- そんな問題も簡単に解けちゃうUnion-Findは強力なツールじゃないだろうか（やや自信なし）