Union-Find
Union-Find とは 素集合データ構造を扱うアルゴリズム。 つまり、グループ分けを扱える。ただし、1 つの要素が複数のグループに属することはない。 Union-Find のアルゴリズム Union-Find には、主に Union と Find の 2 つの操作がある。 Union(x,y) 要素 x を含むグループと要素 y を含むグループを統合する。x と y が同じグループなら何もしない。 Find(x) 要素 x を含むグループの値 (例えば、グループの代表の要素) を返す。 実装方法 高速に Union-Find を行うには、それぞれのグループを木とした素集合森でデータを扱うとよい。それぞれ、木の根をグループの代表者とみなす。初期状態において、各要素は自分のみのグループに属する。 Union と Find それぞれを工夫することで高速化を図る。Union は Find を用い、それ以外の部分は \(O(1)\) であるため、Union と Find の計算量は同じである。 Union 2 つの木の高さまたは要素数を比較し、小さいほうの根を大きいほうの根に連結する。どちらか好きなほうを実装すればよい。 どちらを用いても、Union または Find の計算量は、\(O(\log n)\)。 また、Find の高速化で木の高さが減少することがあるため、Find の高速化と併用すると正確な木の高さは取得できなくなることに注意。要素数は変わらないため、取得できるようにしておくといいことがあるかも (競プロで使うことはある)。 Find Find の計算量は木の高さ (Find する要素と根の距離) に依存する。そのため、Find しながら木の高さを減らしていく。以下の 3 つのうち好きなものを実装すればよい。 ・path compression [Find する要素] の親を新たな要素とする。これを要素が根になるまで続ける。根まで到達したら、辿ったすべての要素の親を根に書き換える。 ・path splitting [Find する要素の親, 要素の親の親] を新たな [要素, 要素の親] とする。これを要素が根になるまで続ける。 ・path halving Find する要素の親を要素の親の親に書き換える。その後、要素の親 (元...