Implementation:UnionFindSetおよびルックアップセット

class UnionFindSet {

    private:

        int *pref;

        int *rank;

        int capacity;

    public:

        UnionFindSet(int n) {

            if (n <= 0) {

                capacity = 0;

                return;

            }

            capacity = n;

            pref = new int[n];

            rank = new int[n];

            for (int i=0; i<n; i++) {

                rank[i] = 0;

                pref[i] = i;

            }

        }

        

        int find(int s) {

            if (s >= capacity || s < 0) return -1;

            if (s == pref[s]) return s;

            return pref[s] = find(pref[s]);

        }

        

        void unite(int a, int b) {

            if (a >= capacity || b >= capacity || a < 0 || b < 0) return;

            int pa = find(a), pb = find(b);

            if (pa == pb) return; // already united

            if (rank[pa] < rank[pb]) {

                pref[pa] = pb;

            } else {

                pref[pb] = pa;

            }

            if (rank[pa] == rank[pb]) rank[pa]++;

        }

        

        bool same(int a, int b) {

            return find(a) == find(b);

        }

};

セットを調べて練習します