并查集的封装操作

2018-10-10 21:03:59


为了装X使我们的代码更加有条理,我们应当用类对一些特定的一组结构进行封装,既然要装X学习这种操作,那我们就先从最简单的并查集开刀了解吧!

先提一下并查集的英文名叫做DisjointSet,亦或是UnionFindSet,支持find,merge两种操作,特定的情境下可以将并查集的功能进行拓展,这里是带路径压缩启发式合并的基础并查集。

不多说,上代码


[接口] 结构体:DisjointSet 成员变量:vector<int> father; vector<int> rank; 成员函数:find(int v) (O(1)) merge(int x, int y) (O(1)) DisjointSet(int n) (O(n))


class DisjointSet {
    private:
        vector<int> father, rank;
        int n;
    public:
        DisjointSet(int n) : father(n+1), rank(n+1) {
            for(int i = 1; i <= n; ++i) {
                father[i] = i;
            }
        }

        int find(int v) {
            return father[v] = v == father[v]? v: find(father[v]);
        }

        void merge(int x, int y) {
            int a = find(x), b = find(y);
            if(rank[a] < rank[b]) {
                father[a] = b;
            } else {
                father[b] = a;
                if(rank[b] == rank[a]) {
                    ++rank[a];
                }
            }
        }
};