Union-Find - aLife

グラフの節点の中で，その節点に繋がる全ての経路が移動不能になったとき，他のどこかの節点からどこかの節点への経路も絶たれてしまうような節点の数を出力する．上手く説明できないけど，要はグラフの連結成分を数えれば良い．

グラフの連結成分を数えるには，深さ優先探索しながらIDを振っていくという方法があるけど，N=100なこの場合，密グラフに対しては実行時間がちょっと不安．そこで登場するのがunion-findというデータ構造．

CLRによるとUnion-Find disjoint setというのが正式名称らしい．disjoint setというのは互いに素な集合のこと．で，unionとfindというのがこのデータ構造に対する操作のことで，統合と検索を意味する．

union-findは単純なグループ化をイメージすると分かりやすい．最初は全ての要素が別々のグループに所属している．要素数がnならグループ数もn個ある．そのうち，問題の定義によって同一と見なせる要素を見つけたら（find），それらを統合し（union）同じグループに所属させる．これを繰り返していくと，同じ特徴をもった要素は同じグループに所属し，また，ある要素が同時に複数のグループに所属することはないような状態になる．この問題だと，節点を要素としてもって，互いに到達可能な節点を同じグループに所属させるようにすることで上手くいく．

union-find自体は有用なデータ構造だが．これを効果的に使える問題というのがuvaにはあまりない．そういった点では，この問題はunion-findの練習台として丁度良さそう．