| 
"データ構造をマージする一般的なテク" という言葉がじわじわとプログラミングコンテスト界隈に広まっている感じがします．「聞いたことがある表現だなあ」と思っていたらどうやら僕がそう呼んだせいらしい（ソース1, ソース2）．
皆 Building 2 なんてマニアック気味な問題の解説をよく読んでいるなあと思います．難しめの問題の細部ということでスライドでは端折り気味になっており申し訳ないなあと思いますので，改めてこっそり解説をしておきます．
Union-Find のデータ構造といえば以下をサポートするものです．
親を覚えてツリーを作ってグループを表現する手法をご存知だと思います．（あの計算量にアッカーマン関数の逆関数が出てくるやつです．ご存じなければこのスライドをどうぞ．）
しかし，以下ではそれとは違うアプローチでこれを効率的に実現します．（ちなみにその親を覚える手法は，以下の手法と区別するときは Quick Union などと呼ばれるようです．)
以下のプログラムは Union-Find のデータ構造を何も知らない人に「これらの機能を実現して」と言った時にそこそこ書かれる可能性のある感じのものじゃないかと思います．
vector<int> i2g; // i2g[i] := アイテム i の所属するグループの番号 vector<vector<int>> g2i; // g2i[g] := グループ g に所属するアイテムたち void init(int n) { i2g.resize(n); g2i.resize(n); for (int i = 0; i < n; ++i) { // 最初はアイテム i はグループ i に所属 i2g[i] = i; g2i[i].assign(1, i); } } // アイテム ia の所属するグループとアイテム ib の所属するグループを 1 つにする // （ia と ib は違うグループに所属するものとする） void merge(int ia, int ib) { int ga = i2g[ia], gb = i2g[ib]; // グループ gb に所属する全てのアイテムをグループ ga に移す for (int j : g2i[gb]) i2g[j] = ga; g2i[ga].insert(g2i[ga].end(), g2i[gb].begin(), g2i[gb].end()); g2i[gb].clear(); } // アイテム ia とアイテム ib は同じグループに所属しているか？ bool is_same_group(int ia, int ib) { return i2g[ia] == i2g[ib]; }
残念ながら，お気づきの通り，偏って merge されまくると merge に毎回 Θ(n) 時間かかり計算量が全体で Θ(n^2) になってしまいお話にならない感じです．
ちなみに，一応，こいつには Quick Find アルゴリズムという名前がついているっぽいです．まあ確かに関数 is_same_group は O(1) 時間なので Quick という名を冠していることを辛うじて許してやろうか．
しかし，なんと実は，上のアプローチは以下のように merge にほんの少し手を加えるだけで一気に優等生になります．
void merge(int ia, int ib) { // ia の所属するグループが ib の所属するグループより小さくならないようにする if (g2i[i2g[ia]].size() < g2i[i2g[ib]].size()) { swap(ia, ib); } // あとはさっきと同じ int ga = i2g[ia], gb = i2g[ib]; for (int j : g2i[gb]) i2g[j] = ga; g2i[ga].insert(g2i[ga].end(), g2i[gb].begin(), g2i[gb].end()); g2i[gb].clear(); }
merge をする時，グループの大小に気をつけ，大きいグループの方はそのままにして，小さいグループの方のアイテムだけを移動するようにする，それだけです．
一見，比較的自明な感じなので，ふつーの定数倍高速化かな？と思われるかもしれません．でも，実はこれは本質的な変化で，なんと merge の計算量は一気にならし O(log n) 時間になります．
ならし O(log n) 時間になるということは，ある視点に気づけば比較的簡単に理解できます．その視点とは，アイテム 1 つずつに注目して考えるということです．
というわけで実は，merge がならし O(log n) 時間で is_same_group が O(1) 時間というまともに使い物になる Union-Find のデータ構造が，こうやっても作れるんですね．これは Quick Find Weighted などと呼ばれるそうです．
（ちなみに，Quick Union に比べて is_same_group はこっちのほうが高速なので，こっちのほうが有利なシチュエーションというのもあるはずです．）
この，大きさに気をつけて小さい方を大きい方にくっつけるという考え方を応用することで，色々な普通のデータ構造にマージ機能を追加することができます．
例えば，std::set<int> がいっぱいあって，全体では n 個の int が記憶されてるとして，これらをがんがんマージしていくという処理をしたい気持ちになったとしましょう．std::set には効率的なマージ機能は用意されていませんが，実は以下のように書くだけでマージ部分の全体の計算量は O(n log^2 n) 時間で抑えられます．さっきと同じく，大きい方に小さい方の中身を全部挿入するだけ．
// a, b をマージする．a に全要素が入り，b が空になる． void merge_set(set<int> *&a, set<int> *&b) { // b のほうが a よりサイズが小さいようにして if (a->size() < b->size()) swap(a, b); // a に b の中身を全部入れるだけ a->insert(b->begin(), b->end()); b->clear(); }
これは，挿入がサポートされているデータ構造なら何でもできます．一般的だ！*1 挿入が O(ほげ) のデータ構造なら，全体の計算量は O(n log n * ほげ) になります．
他でも何度か使った気がするけれどすぐに思い出せるのはこれぐらいかなあ．ご存知なのあれば是非教えてください．