DS | 并查集

c++实现

class UnionFindSet {
private:
    vector<int> father;
public:
    UnionFindSet(int size) {
        for(int i = 0; i < size;i++) {      //并查集初始化
            father.push_back(i);
        }
    }
    int findFather(int x) {     //查找，路径压缩
        int a = x;
        while(x != father[x]) {
            x = father[x];
        }
        while(a != father[a]) {
            int z = a;
            a = father[a];
            father[z] = x;
        }
        return x;
    }
    void Union(int a, int b) {      //合并
        int faA = findFather(a);
        int faB = findFather(b);
        if(faA != faB){
            father[faA] = faB;
        }
    }
};

例子

leetcode-959

class UnionFindSet { ... };
class Solution {
public:
    int regionsBySlashes(vector<string>& grid) {
        //利用并查集，每次加入的边若能够形成一个新环（即两个节点的根节点相同）则区域+1
        int result = 1, n = grid.size() + 1;
        UnionFindSet ufs(n*n);
        //加入正方形边长
        for(int i = 0; i < n - 1; i++) {    //横边
            ufs.Union(i, i + 1);
            ufs.Union((n - 1) * n + i, (n - 1) * n + i + 1);
        }
        for(int i = 0; i < n - 1; i++) {    //竖边
            ufs.Union(i * n, (i + 1) * n);
            ufs.Union((i + 1) * n - 1, (i + 2) * n - 1);
        }
        //逐步合并
        for(int i = 0; i < n - 1; i++) {
            for(int j = 0; j < n - 1; j++) {
                if(grid[i][j] == ‘ ‘) {
                    continue;
                }else if(grid[i][j] == ‘/‘) {
                    int b = (i + 1) * n + j;
                    int a = b - n + 1;
                    if(ufs.findFather(a) == ufs.findFather(b)) result++;
                    ufs.Union(a,b);
                }else {
                    int a = i * n + j;
                    int b = a + n + 1;
                    if(ufs.findFather(a) == ufs.findFather(b)) result++;
                    ufs.Union(a,b);
                }
            }
        }
        return result;
    }
};

DS | 并查集

原文：https://www.cnblogs.com/einsier/p/14325329.html