Union-Find (連結成分数)

報告が 1 件届くたびに、全体を歩き直したくない

利用者アカウントが 6 件あり、「この 2 つは同一人物でした」という報告が 1 件ずつ届きます。届くたびに「今いくつのグループに分かれているか」を答えたい。報告のたびに全体をたどり直すと、報告の数だけ全員を歩くことになります。しかも歩く先は、前回とほとんど同じ場所です。

しかし、ここで知りたいのは経路ではありません。「同じ組かどうか」だけです。それなら、組ごとに代表を 1 人決めておけば足ります。

代表を 1 人決める

各要素に「親」を 1 つだけ持たせます。最初は全員が自分自身を親にしていて、これは「全員が別の組」という状態です。

代表を聞かれたら、親をたどって、自分自身が親になっているところまで登ります。そこが組の代表です。途中に何件はさまっていても、行き着く先が同じなら同じ組です。2 つを同じ組にするときは、まずそれぞれの代表まで登り、片方の代表の親を、もう片方の代表にします。付け替えるのは代表 1 つだけで、組の中の全員を書き換える必要はありません。

報告が 3 件届いたときの親の並びは、次のように変わります。

最後に全員の代表を聞くと、0 と 2 と 3 は代表が 3、4 と 5 は代表が 5、1 は自分のままです。数えるのは人数ではなく代表の種類なので、組は 3 つです。誰とも結ばれなかった 1 も、自分が代表のまま 1 組として数えられます。

すでに同じ組の 2 つを結ぶ報告や、自分自身への報告が来ることもあります。代表が同じなら何もしない、という分岐を入れておけば、そのまま素通しできます。

この持ち方が向くのは、つながりが後から 1 本ずつ増えていく場面です。つながりが最初から全部そろっていて、数えるのが 1 回きりなら、探索で数えても手間は変わりません。報告が届くたびに答えたい、という状況ではじめて差がつきます。

たどる道を短くしておく

この仕組みの弱点は、つなぎ方によって親の鎖が長くなることです。一直線に伸びてしまうと、代表を聞くたびに端から端まで登ることになり、せっかくの速さが出ません。

工夫は 1 つ入れれば十分です。代表を聞かれてたどったついでに、通ったところの親を代表に付け替えておきます。次からは 1 歩で代表に着くので、同じ場所を何度も登らずに済みます。答えは何も変わらず、たどる距離だけが縮みます。代表を聞くほど道が整理されるので、使い込むほど速くなる、という珍しい形の工夫です。

解説

覚え方 ... 代表が同じなら同じ組。組を数えるのは、代表の種類を数えること。

1. parent 配列で各ノードの代表元を管理する Union-Find を実装する
2. find は親を辿ってルートを返す。path compression を入れると効率的
3. 最後にユニークなルート数を数えて返す