并查集的C++实现

这里只写了实现和应用。

理论部分可以参考下面的链接：
https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86
https://www.runoob.com/data-structures/union-find-basic.html

1. C++实现

1. 并查集实现是可以分为有rank和无rank。
2. 有rank的实现在合并的时候，把rank小的挂在rank大的上面，一定程度上能提高效率。
3. 无rank代码稍微简单一些，看起来比较清晰

1.1 有rank

合并的时候，把rank小的挂在rank大的上面，一定程度上能提高效率

class UnionFindSet {
public:
    UnionFindSet(int num_vertex) {
        num_vertex_ = num_vertex;
        father_     = vector<int>(num_vertex_);
        rank_       = vector<int>(num_vertex_);
    }

private:
    void make_set() {               //初始化集合，让所有的点都各成一个集合，每个集合都只包含自己
        for (int i = 0; i < num_vertex_; i++) {
            father_[i] = i;
            rank_[i] = 1;
        }
    }

    int find_set(int x) {           //判断一个点属于哪个集合，点如果都有着共同的祖先结点，就可以说他们属于一个集合
        if (x != father_[x]) {
            father_[x] = find_set(father_[x]);
        }
        return father_[x];
    }

    void union_set(int x, int y) {  //将x,y合并到同一个集合
        x = find_set(x);
        y = find_set(y);

        if (x == y) { return; }

        if (rank_[x] < rank_[y]) {
            father_[x] = find_set(y);
        }
        else {
            if (rank_[x] == rank_[y]) { rank_[x]++; }

            father_[y] = find_set(x);
        }
    }

    int             num_vertex_;
    vector<int>     father_;
    vector<int>     rank_;
};

1.2 无rank

class UnionFindSetNoRank {
public:
    UnionFindSetNoRank(int num_vertex) {
        num_vertex_ = num_vertex;
        father_ = vector<int>(num_vertex_);
        make_set();
    }
    
    void make_set() {               //初始化集合，让所有的点都各成一个集合，每个集合都只包含自己
        for (int i = 0; i < num_vertex_; i++) {
            father_[i] = i;
        }
    }

    int find_set(int x) {           //判断一个点属于哪个集合，点如果都有着共同的祖先结点，就可以说他们属于一个集合
        if (x != father_[x]) {
            father_[x] = find_set(father_[x]);
        }
        return father_[x];
    }

    void union_set(int x, int y) {  //将x,y合并到同一个集合
        x = find_set(x);
        y = find_set(y);

        if (x == y) { return; }

        father_[y] = x;
    }

private:
    int             num_vertex_;
    vector<int>     father_;
};

下面的实现跟上面一样，只是函数名使用驼峰命名法，上面的是下划线分割法

class UnionFindSetNoRank {
public:
    UnionFindSetNoRank(int num_vertex) {
        num_vertex_ = num_vertex;
        father_ = vector<int>(num_vertex_);
        makeSet();
    }

    void makeSet() {               //初始化集合，让所有的点都各成一个集合，每个集合都只包含自己
        for (int i = 0; i < num_vertex_; i++) {
            father_[i] = i;
        }
    }

    int findSet(int x) {           //判断一个点属于哪个集合，点如果都有着共同的祖先结点，就可以说他们属于一个集合
        if (x != father_[x]) {
            father_[x] = findSet(father_[x]);
        }
        return father_[x];
    }

    void unionSet(int x, int y) {  //将x,y合并到同一个集合
        x = findSet(x);
        y = findSet(y);

        if (x == y) { return; }

        father_[y] = x;
    }

private:
    int             num_vertex_;
    vector<int>     father_;
};

2. 应用

leetcode 547. 省份数量
https://leetcode-cn.com/problems/number-of-provinces/

思路： 查找连通域的个数

class Solution {
public:
    int findCircleNum(vector<vector<int>>& isConnected) {
        int N = isConnected.size();

        num_vertex_ = N;
        father_ = vector<int>(num_vertex_);
        rank_ = vector<int>(num_vertex_);
        make_set();

        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                if (isConnected[i][j]) {
                    union_set(i, j);
                }
            }
        }

        int count = 0;
        for (int i = 0; i < N; ++i) {
            if (father_[i] == i) {
                count++;
            }
        }

        return count;
    }

private:
    void make_set() {               //初始化集合，让所有的点都各成一个集合，每个集合都只包含自己
        for (int i = 0; i < num_vertex_; i++) {
            father_[i] = i;
            rank_[i] = 1;
        }
    }

    int find_set(int x) {           //判断一个点属于哪个集合，点如果都有着共同的祖先结点，就可以说他们属于一个集合
        if (x != father_[x]) {
            father_[x] = find_set(father_[x]);
        }
        return father_[x];
    }

    void union_set(int x, int y) {  //将x,y合并到同一个集合
        x = find_set(x);
        y = find_set(y);

        if (x == y) { return; }

        if (rank_[x] < rank_[y]) {
            father_[x] = find_set(y);
        }
        else {
            if (rank_[x] == rank_[y]) { rank_[x]++; }

            father_[y] = find_set(x);
        }
    }

    int             num_vertex_;
    vector<int>     father_;
    vector<int>     rank_;
};