UnionFindのなかま

2021/12月に行われた大LTでの発表資料です

イベントページはこちら
https://zli.connpass.com/event/230124/

Transcript

1. UnionFind のなかま 会津大学 学部 2 年 松本響輝 タイトルついでの⾃⼰紹介 • 会津⼤学コンピュータ理⼯学部コンピュータ理⼯学科（⾧い） • 最近はまってるのはライブラリ作成 ◦ https://github.com/matumoto1234/library/ • Nuxt.js や C++ をたまにやる • 競技プログラミングが好き ◦ AtCoder ⽔ 💧 • ゲーム開発も好き
2. UnionFind ってご存じですか？
3. それとなく分かる UnionFind • UnionFind は素集合を管理するデータ構造 ◦ 素集合とは？ 素集合・・・どの集合も要素の交わりを持たない A B
4. それとなく分かる UnionFind • UnionFind でできること ◦ 連結 ならしO( α (N) ) ▪ merge(x, y) := x と y が属する集合をくっつける ◦ 判定 ならしO( α (N) ) ▪ same(x, y) := x と y が属している集合が同じかどうか ※ N は管理する値の数
5. UnionFind の仕組み • 木構造になっている 0 1 2 3 4 すでにそれぞれが要素数 1 の集合
6. UnionFind の仕組み • merge(0, 1) が使われると 0 1 2 3 4
7. UnionFind の仕組み • 続いて merge(2, 3) が使われると 0 1 2 3 4
8. UnionFind の仕組み • 続いて merge(2, 4) が使われると 0 1 2 3 4
9. UnionFind の仕組み • 続いて merge(1, 3) が使われると 0 1 2 3 4
10. それとなく分かる UnionFind • UnionFind でできないこと ◦ 辺の削除 ▪ erase(x, y) := x と y を繋ぐ辺を削除 ◦ その他 ▪ UnionFind でできること以外
11. 実は UnionFind には たくさんの親戚がいます！
12. ～ UnionFind の 森 ～ ここは UnionFind の 森 様々な UnionFind たちを かんさつ できます
13. おや...？
14. 仲間になりたそうにこちらを見ています じー
15. 近づいて かんさつ してみますか？ ➢ はい Yes
16. 彼を かんさつ します...
17. 彼の正体は QuickFind だったようです！ 0 1 2 3 4 0 4 3 1 2
18. それとなく分かる QuickFind • QuickFind は UnionFind と計算量が違う ◦ 連結 O( N ) ▪ merge(x, y) に O( N ) かかってしまう ◦ 判定 O( 1 ) ▪ same(x, y) は O( 1 ) ですむ
19. QuickFind の仕組み • 配列で管理 0 1 2 3 4 0 1 3 2 4
20. QuickFind の仕組み • merge(0, 1) が行われると 0 1 2 3 4 0 1 3 2 4
21. QuickFind の仕組み • 続いて merge(2, 3) が行われると 0 1 2 3 4 0 1 3 2 4
22. QuickFind の仕組み • 続いて merge(2, 3) が行われると 0 1 2 3 4 0 1 3 2 4
23. QuickFind の仕組み • 続いて merge(0, 2) が行われると 0 1 2 3 4 0 1 3 2 4
24. QuickFind の仕組み • 続いて merge(0, 2) が行われると 0 1 2 3 4 0 1 3 2 4
25. QuickFind の仕組み • 続いて merge(2, 4) が行われると 0 1 2 3 4 0 1 3 2 4
26. QuickFind の仕組み 0 1 2 3 4 0 1 3 2 4 • 続いて merge(2, 4) が行われると
27. QuickFind は去っていきました
28. おや...？
29. 仲間になりたそうにこちらを見ていません …
30. それでも近づいて かんさつ してみますか？ ➢ YESYESYES はいはいはい
31. 彼を かんさつ します...
32. かんさつ する前に逃げられてしまった！
33. しかし追いつけたので問題ありません
34. 彼の正体は Undo 可能 UnionFind だったようです！ 0 1 2 3 4
35. それとなく分かる Undo 可能 UnionFind • Undo 可能とは？ ◦ 操作列を stack で管理することで Undo を可能にした • デメリット ◦ 経路圧縮 という工夫ができなくなり、計算量が大きくなる O( α (N) ) → O( log N ) 詳細は略
36. Undo 可能 UnionFind は去っていきました
37. おや...？
38. 大きな 森 が近づいてきました
39. 大きな 森 が近づいてきました
40. 大きな 森 が近づいてきました
41. かんさつ してみましょう
42. 彼の正体は 削除可能 UnionFind だったようです！
43. それとなく分からない 削除可能 UnionFind • 削除可能とは？ ◦ 平衡二分探索木を中に取り入れた Linc Cut 木 (Euler Tour Tree) を使って削 除を可能にした ◦ そもそもデータ構造としての格が違う • デメリット ◦ できなかったことを可能にしているので計算量が大きくなる O( α (N) ) → O( log2 N ) 詳細は略
44. 削除可能 UnionFind は去っていきました
45. どうやら近くの UnionFind はいなくなってし まったようです...
46. ご清聴ありがとうございました！ 紹介しきれなかった親戚 • 部分永続 UnionFind • 完全永続 UnionFind • 重み付き UnionFind • 重み付き Undo 可能 UnionFind など