Union-Find (連結成分数)

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

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

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

代表を 1 人決める

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

const parent = [0, 1, 2, 3, 4, 5];

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

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

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

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

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

たどる道を短くしておく

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

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

解説

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

最初の演習は親をたどるだけ

経路圧縮は後から速くする工夫です。この演習では、親を書き換えずに代表を探します。

parent = [1, 2, 2]
x = 0
while parent[x] != x:
    x = parent[x]
print(x)  # 2

まず「同じ代表なら同じ組」を確かめます。長い鎖では探索に時間がかかりますが、代表の答えは変わりません。

演習の findRoot(parent, x) は countComponents と同じ段に置き、親の配列も引数で渡します。たとえば findRoot(parent, 0) で 0 の代表を尋ねます。入れ子の関数は使いません。結合と代表の種類の集計は変更不要な配布コードで、親をたどる本体だけを完成させます。

1. parent を引数で受け取る findRoot を完成させる
2. parent[x] が x と等しくなるまで親をたどる
3. 代表を返し、結合と種類の集計は用意済みの処理へ渡す