并查集 - L

并查集概念

并查集是一种用来管理元素分组情况的数据结构。并查集可以高效地进行如下操作。

查询元素a和元素b是否属于同一组。

合并元素a和元素b所在的组。

模板

class DisjointSets{
private:
    vector<int> parent, rank;

public:
    DisjointSets(int num) {
        parent = vector<int>(num, 0);
        rank = vector<int>(num, 0);
        for (int i = 0; i < num; i++) {
            parent[i] = i;
        }
    }

    int find(int p) {
        if(p == parent[p])
            return p;
        parent[p] = find(parent[p]);
        return parent[p];
    }

    void unionTwo(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ) return;
        if (rank[rootQ] > rank[rootP]) {
            parent[rootP] = rootQ;
        }else {
            parent[rootQ] = rootP;
            if (rank[rootP] == rank[rootQ]) {
                rank[rootP]++;
            }
        }
    }  

};

Disjoint Sets （以下简称DS）的本质是许多棵树。每个圈子里的元素都组成了一棵树。然而我们的表示方法并不是用常规tree node的方法记录的，而是用数组.

DS里面拥有一个大小为N的vector parent，对于parent[i],存储着第i号元素所属圈子的老大。DS里面的另一个vector rank用来存储树的高度，它的作用会在Union操作中体现出来。

DS里面经典的两个操作分别是find和Union.

find

find就是寻找这个圈子的老大（这棵树的root）。对于find来说，在寻找root的过程中，我们不仅要找到root，还要把沿途经过的所有node的parent都变成root，也就是把自己和沿途所有的node都变成root的孩子（同时也变成了深度为1的leaf）。这个操作叫path compression，意义在于下次我们如果寻找这些node的老大，就可以一步到位了（直接通过parent[i]找到root）。这对时间复杂度的优化是非常重要的。

Union

Union是什么？是我们知道了两个元素属于同一个圈子。如果我们的DS已经知道这一点，那么没问题，如果我们的DS不知道这一点，我们要告诉它。并且很重要的是，这里不是针对两个元素，而是要把这两个元素所处的两个圈子融合成一个圈子，这也就是Union叫法的由来。那么我们分别用find找到两个元素所处tree的root，然后通过比较rank[root]的大小看哪棵树更大。最后我们把小的那棵树的root变成大的那棵树的root的孩子。之所以要选择把小的那棵树融合进大的那棵树，是因为我们希望让树的孩子的高度都尽量小。假设小的树的孩子数量是N1，大的树的孩子数量是N2。如果把小数融合进大树，那么我们让N1个node的高度都增加了1，反之我们要让N2个node的高度都增加1。后者明显是违反我们希望让树的孩子的高度都尽量小这个意愿的。
Disjoint Sets using union by rank and path compression Graph Algorithm中以具体的例子演示了Union的过程。

例题

Friend Circles

class Solution {
public:
    class DisjointSets{
    private:
        vector<int> parent, rank;
        int count;

    public:
        DisjointSets(int num) {
            count = num;
            parent = vector<int>(num, 0);
            rank = vector<int>(num, 0);
            for (int i = 0; i < num; i++) {
                parent[i] = i;
            }
        }

        int find(int p) {
            if(p == parent[p])
                return p;
            parent[p] = find(parent[p]);
            return parent[p];
        }

        void unionTwo(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;
            count -= 1;
            if (rank[rootQ] > rank[rootP]) {
                parent[rootP] = rootQ;
            }else {
                parent[rootQ] = rootP;
                if (rank[rootP] == rank[rootQ]) {
                    rank[rootP]++;
                }
            }
        }  

        int getCount() {
            return count;
        }

    };
    int findCircleNum(vector<vector<int>>& M) {
        DisjointSets ds(M.size());
        for (int i = 0, n = M.size(); i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                if (M[i][j]) ds.unionTwo(i, j);
            }
        }
        return ds.getCount();
    }
};

对于整个matrix，如果M[i][j]为1，我们则需要告诉DS i和j属于一个圈子。这里因为对称性，我们只需要遍历半个matrix就可以得到所有信息。在DS里面我增加了一个count。count代表现在DS中独立圈子的数量。因为最开始我们什么信息都不知道，假设每个人都属于自己的独立圈子，所以count为人的个数，之后每一次Union操作，如果我们发现i和j所处圈子（的老大）不同（root1 ！= root2），那么说明有两个圈子要合并成一个，那么就少了一个圈子，所以count要减1.最后我们返回count，也就是圈子的数量。

Number of Islands

class Solution {
public:
    class DisjointSets{
    private:
        vector<int> parent, rank;
        int count;

    public:
        DisjointSets(int num) {
            count = num;
            parent = vector<int>(num, 0);
            rank = vector<int>(num, 0);
            for (int i = 0; i < num; i++) {
                parent[i] = i;
            }
        }

        int find(int p) {
            if(p == parent[p])
                return p;
            parent[p] = find(parent[p]);
            return parent[p];
        }

        void unionTwo(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;
            count -= 1;
            if (rank[rootQ] > rank[rootP]) {
                parent[rootP] = rootQ;
            }else {
                parent[rootQ] = rootP;
                if (rank[rootP] == rank[rootQ]) {
                    rank[rootP]++;
                }
            }
        }  

        int getCount() {
            return count;
        }

    };
    
    int numIslands(vector<vector<char>>& grid) {

        if(grid.size() == 0 || grid[0].size() ==0)
            return 0;
        int m = grid.size();
        int n = grid[0].size();
        int num = 0;
        unordered_map<int, int> hashMap;
        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(grid[i][j] == '1'){
                    hashMap[i*n+j] = num;
                    num++;
                }
            }
        }

        DisjointSets ds(num);   

        for(int i = 0; i < m; ++i){
            for(int j = 0; j < n; ++j){
                if(grid[i][j] == '1'){
                    if(i - 1 >= 0 && hashMap.count((i-1)*n+j)){
                        ds.unionTwo(hashMap[(i-1)*n+j], hashMap[i*n+j]);
                    }
                    if(i + 1 < m && hashMap.count((i+1)*n+j)){
                        ds.unionTwo(hashMap[(i+1)*n+j], hashMap[i*n+j]);
                    }
                    if(j - 1 >= 0 && hashMap.count(i*n+j-1)){
                        ds.unionTwo(hashMap[i*n+j-1], hashMap[i*n+j]);
                    }
                    if(j + 1 < n && hashMap.count(i*n+j+1)){
                        ds.unionTwo(hashMap[i*n+j+1], hashMap[i*n+j]);
                    }
                }
            }
        }
        return ds.getCount();

    }
};

参考资料：

文章目录

并查集概念

模板

find

Union

例题

Friend Circles

Number of Islands