Merge Tech
コードについての説明
"データ構造をマージする一般的なテク"と呼ばれているもの.
例えば, $a = \{ 1,3,5,7,9,11 \}, b = \{ 2,4 \}$ という vector を一つにマージしようとしたとき $a$ の要素を $b$ に移すか, $b$ の要素を $a$ に移すかの2通りが考えられる.
もちろん, 移動させる要素の数が少ない方, つまり $b$ の要素を $a$ に移したほうがよい. 重要な事実としてこのように大きい方に小さい方の要素を移すようにマージを行って要素数 $n$ の集合が得られたとき,
それまでに行われた要素の移動回数は $\O (n \log n)$ になることが帰納法などを用いて言える(何も考えずマージしていると最悪 $\O (n^2)$ かかってしまう).
以上は vector の話だが, set や priority_queue にも上記のテクニックが使え, その場合は一度の要素の移動に $\O (\log n)$ かかるので全体で $\O (n \log^2 n)$ の計算量となる.
以下の実装は vector に対してマージテクを使ったもので UnionFind の強化版、 連結性だけでなく各連結成分の要素も保持できるようなデータ構造となっている.
時間計算量: マージ ならし $\O (\log n)$
コード
class MergeTech{
private:
int sz;
public:
vector<int> par; //所属しているグループ番号(par[x]はunion findのfind(x)に対応)
vector<vector<int> > group; //group[x]:グループxに含まれる数
MergeTech(){}
MergeTech(int node_size) : sz(node_size), par(sz), group(sz){
for(int i = 0; i < sz; i++){
par[i] = i, group[i].push_back(i);
}
}
bool same(int a,int b){ return par[a] == par[b]; }
void unite(int a,int b){
if(same(a,b)) return;
if(group[par[a]].size() < group[par[b]].size()) swap(a,b);
int ga = par[a], gb = par[b];
for(int u : group[gb]){
par[u] = ga;
}
group[ga].insert(group[ga].end(),group[gb].begin(),group[gb].end());
group[gb].clear();
}
};