Union-Find (Disjoint Set Union) のキソのキソ

はじめに

この記事は Competitive Programming (1) Advent Calendar 2020 2日目の記事です。

みなさんこんにちは
今回、なんとなく気が向いたので Union-Find についての記事を書いてみることにしました。
この手の記事はすでに飽和しているとは思いますが、もし誰かの助けになったりしたらうれしいです。

なんとなく自分がそうだと思っているものを書いていくので、間違いなどあるかもしれません。もし見つけたら、優しく教えていただけると嬉しいです。¹

Union-Find とは

Union-Find とは、素集合データ構造のことです。AtCoder Library さんでは、Disjoint Set Union (dsu) という名称が使われているようですが、自分は Union-Find という呼び方になれているので、本記事ではこちらの呼び方で統一しようと思います。

さて、前提知識がない人がいきなり

Union-Find とは、素集合データ構造のことです。

なんて言われても困ってしまうと思います。詳しく説明していきます。

このデータ構造では、頂点の集合に対してこれからいう二つの操作を高速に行うことができます。

• 2頂点を結ぶ辺を追加する
• 2頂点が連結かどうかを判定する

これがどういう意味なのかというと、

まずはじめに $n$ 個の点がバラバラに存在しています。これらの点と点をいくつか線でつないであげます。

この時、この点とその点はつながっていますか？ という質問に対して高速に答えたい！！ ということです。

実装のイメージ

それでは、どうやってそれを実現すればいいのでしょうか。

ここで、$n$ 個の頂点それぞれに、$0$ から $n-1$ の番号をつけてあげることにします。

そして、連結である頂点の集合（つまり、辺をいくつか通って行き来ができる頂点）を一つのグループとしてあげて、そのグループの代表となる頂点を一つ決めるということを考えます。

例えば、$5$ つの頂点 $0,1,2,3,4$ があったとして、$0,1,2$ が一つのグループ、$3,4$ が一つのグループとなっているとしましょう。

このとき、 $0,1,2$ の代表を $0$ 、 $3,4$ の代表を $3$ にしたとします。

ここで質問が来ます

「$1$ と $2$ は連結ですか？」

$1$ と $2$ は連結なので、Yes と答えたいです。そのために、$1$ と $2$ は連結か？ということを $1$ が属しているグループの代表と $2$ が属しているグループの代表は同じか？ということに言い換えてみましょう。

$1$ が属しているグループの代表は $0$ ということにしました。$2$ が属しているグループの代表も同じく $0$ です。どちらも $0$ なので、この二つの頂点は連結です！

と、このような判定をしていきます。

では、

「 $1$ と $3$ を辺で結んでください！」

と言われたとします。これに対してはどう対処するのがいいでしょうか？

ここでは、「どことどこが直接つながっているか」というのは割とどうでもいい情報なので、 $1$ が属しているグループと、$3$ が属しているグループを合体させることだけを考えます。

$1$ が属しているグループの代表は $0$ 、 $3$ が属しているグループの代表は $3$ なので、そのまま合体させると代表が二人になってしまいます。ということで、片方は代表を解任させてもう片方を合体した後のグループ全体の代表ということにしましょう！

とりあえず、 $0$ のほうを新しい代表にするとしてみましょう。すると、もともとの $0$ のグループは何もしなくてもいいのですが、$3$ が代表だったグループに属している頂点すべてに、「新しい代表は $0$ です！」ということを言わなければいけません。これでは、少し時間がかかってしまいそうですね。

ということで、$3$ に対してだけ、「新しい代表は $0$ です！」と言うことにしましょう。そうすれば、ここの時間が大幅に短縮できるはずです！

それでは、$3$ が代表だったグループに属していたほかの頂点はどうなってしまうのでしょうか？
ここでは、 $4$ がそれにあたりますが、まだ $4$ は代表が $3$ だと思っています。しかし、「 $4$ の代表の代表」というものを考えてみると、$4$ の代表の代表 = $3$ の代表 = $0$ となり、新しい代表にたどり着くことができます。

自分が代表なら自分を、そうでなければ、代表の代表を自分のグループの代表だと考えると、うまくいきそうです！

それでは、どんな感じになるのか、簡単に書いてみましょう。

「自分のグループの代表」というものを配列で管理することを考えてみましょう。

初めは、どのグループも自分だけなので、代表は自分です。

頂点番号	$0$	$1$	$2$	$3$	$4$	$\ldots$	$n-1$
代表の番号	$0$	$1$	$2$	$3$	$4$	$\ldots$	$n-1$

$0$ と $3$ を連結してみます

頂点番号	$0$	$1$	$2$	$3$	$4$	$\ldots$	$n-1$
代表の番号	$0$	$1$	$2$	$0$	$4$	$\ldots$	$n-1$

$2$ と $4$ を連結してみます

頂点番号	$0$	$1$	$2$	$3$	$4$	$\ldots$	$n-1$
代表の番号	$0$	$1$	$2$	$0$	$2$	$\ldots$	$n-1$

$3$ と $4$ を連結してみます

頂点番号	$0$	$1$	$2$	$3$	$4$	$\ldots$	$n-1$
代表の番号	$0$	$1$	$0$	$0$	$2$	$\ldots$	$n-1$

とまあ、こんな感じになるわけですね

高速化のための工夫

しかし、ここで問題が起こります

代表の代表を自分のグループの代表だと考える という方針にしたのですが、もしもグループの合体が何度も起きて、代表が塗り替わり続けると、代表探しに時間がかかるようになってしまいます

どういうことか？といいますと、

これが

頂点番号	$0$	$1$	$2$	$3$	$4$	$\ldots$	$n-1$
代表の番号	$0$	$1$	$2$	$3$	$4$	$\ldots$	$n-1$

こうなってしまう

頂点番号	$0$	$1$	$2$	$3$	$4$	$\ldots$	$n-1$
代表の番号	$0$	$0$	$1$	$2$	$3$	$\ldots$	$n-2$

可能性があるわけです

ここで 「$n-1$ の代表はだれですか？」 と聞かれた場合、
$n-1$ の代表の $n-2$ の代表の $n-3$ の代表の .... $2$ の代表の $1$ の代表の $0$ です！

ということで最悪の場合計算量は $O(N)$、ここにとても時間がかかってしまうわけですね

こうならないために、人々は二つの工夫を考えだしました

一つ目は、グループを合体するときに、どちらを新しい代表にするのか という部分です

これは union by size と呼ばれるものと、union by rank と呼ばれるものがあります

union by size は、簡単にいうともともとより大きかった方のグループの代表を新しい代表にするということです
代表が変わる人が少ないほうが後から必要になる処理が少なそうですよね？

union by rank は、簡単にいうともともとより「代表の代表の...」の処理が多い方のグループの代表を新しい代表にするということです
そこの処理がネックになっていたので、できるだけ少なくしたいわけですね

どちらのほうがいいのか？ というところを聞かれると困ってしまうのですが、僕は union by size のほうが好きです

計算量はどうなるのか？ という話ですが、実はこれをするだけで $O(logN)$ で抑えることができるようになります！
なんでや！？ というのはぜひ考えてみてください (頂点数がどうなっていくのかな？ を考えてみるといいと思います)

さて、頭のいい人々は $O(logN)$ で満足しませんでした
ということで二つ目の工夫、経路圧縮 が登場します

さきほどの工夫は、グループの合体の仕方の工夫でしたが、今回は、代表を探すときの工夫です

どこを短縮できるんだ？という話なのですが、探し方は同じです
今回の工夫は見つけた後の操作で、その頂点の代表を見つけた代表に塗り替える ということをします

難しそうなことを言っているように感じるかもしれませんがそんなことはなくて、

こうなったときに

頂点番号	$0$	$1$	$2$	$3$	$4$	$\ldots$	$n-1$
代表の番号	$0$	$0$	$1$	$2$	$3$	$\ldots$	$n-2$

「$n-1$ の代表はだれですか？」 と聞かれたら、まず頑張って探します
代表の代表の...　としていって $0$ が見つかりますね では、 $0$ です！ と言いながら本当に $0$ に変えてしまいます

頂点番号	$0$	$1$	$2$	$3$	$4$	$\ldots$	$n-1$
代表の番号	$0$	$0$	$1$	$2$	$3$	$\ldots$	$0$

こうすると、次からはすぐに代表がわかります！！

本当は、 $n-1$ だけでなく、代表を探す途中で見た頂点すべてを変えます

頂点番号	$0$	$1$	$2$	$3$	$4$	$\ldots$	$n-1$
代表の番号	$0$	$0$	$0$	$0$	$0$	$\ldots$	$0$

ということで、今回紹介した二つの工夫をしてあげると、(ならし)計算量は驚きの $O(α(N))$ となります！！
$α(N)$ ってなんぞや？ となるかと思いますが、これはアッカーマン関数の逆関数です

アッカーマン関数というのは何なのかというと、指数関数なんかとは比べ物にならないくらい一気に大きくなっていく関数です
気になる人はこういうサイトをみるといいかと思います

要は、そんなにやばい関数の逆関数は、逆に全然大きくならないということです
競プロではほとんど定数と扱っていいのではないかと思います

まとめ

Union-Findは

• 2頂点を結ぶ辺を追加する
• 2頂点が連結かどうかを判定する

が高速に行えるデータ構造だよ！

判定の仕方・合体の仕方・代表の探し方などいろいろな工夫をすることで、とても高速になっているよ！

ちゃんとした実装は載せません (ネットにいくらでもあると思うので)
重み付きUnion-Find 部分永続Union-Find など、いろいろな応用もあったりします
それなりに難しいですが、興味がある人は調べてみると面白いかもしれません

ということで、Union-Find のお気持ちを知る助けになればうれしいな と思います

思ったより時間取れなくて大分雑になってしまったので、そのうち大規模に書きなおすかもしれないです

1. 強くたたかれると泣いてしまうので、お手柔らかにお願いします ↩