Union-Find木を実装する。。。

　最近競プロを始めて、UnionFindを使う問題に出会うことが増えたので実装してみた。

Union-Findとは

　UnionFindは、素集合（互いに素な集合）を求めるアルゴリズムです。

　例えば、グラフのある二つの頂点が連結されているかどうか調べたり、ある頂点にいくつの頂点が繋がっているかなどを調べるためのアルゴリズムです。

コード

　チーター本の実装をアレンジした形になっています。

class UnionFind{
    public:
        vector<int> uni;
        UnionFind(int s) : uni(s, -1) { }
 
       //頂点aが所属するグループを調べる
        int root(int a)
        {
            if (uni[a] < 0) return a;
            return uni[a] = root(uni[a]);
        }
    
        //頂点aと頂点bを繋ぐ。もともと同じグループの時falseを返す
        bool connect(int a,int b)
        {
            a = root(a);
            b = root(b);
            if (a == b) return false;
    
            if (uni[a] > uni[b])
            {
                a ^= b;
                b ^= a;
                a ^= b;
            }
    
            uni[a] = uni[a] + uni[b];
            uni[b] = a;
            return true;
        }
    
        //頂点a,bが同じグループであるかを調べる
        bool isConnect(int a,int b)
        {
            return root(a) == root(b);
        }
    
        //頂点aを含むグループの頂点数を調べる
        int size(int a)
        {
            return -uni[root(a)];
        }
    
    };

　uni配列には

• 親の時、要素数×-1
• 子の時、親の頂点の番号

が入っています。

　ここでは配列を一つにして実装していますが、二つで実装する場合もあるようです。
　

UnionFind 名前(頂点数);

　で宣言します。

まとめ

　アルゴリズムは奥が深いなぁ。。。