并查集

【道德经·第十六章】致虚极，守静笃（dǔ），万物并作，吾以观复。夫物芸芸，各复归其根。归根曰静，是谓复命。复命曰常，知常曰明，不知常，妄作，凶。

本文总结一下并查集在实际问题中的应用，体会一下并查集的精巧的构思^.^。
并查集的教程——来自labuladong

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列的长度。

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        if(nums.size() == 0) 
            return 0;

        int ans = 1;
        for(auto num : nums) {
            mp[num] = 1; cnt[num] = 1; fa[num] = num;
        }

        for(auto num : nums) {
            if(mp[num+1] == 1) {
                ans = max(ans, merge(num+1, num));
            }
        }

        return ans;
    }

    int find(int x) {
        while(x != fa[x]) {
            fa[x] = fa[fa[x]];
            x = fa[x];
        }
        return x;
    }

    int merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if(rootX == rootY) {
            return cnt[rootX];
        }

        int _cnt = 0;
        if(cnt[rootX] > cnt[rootY]) {
            fa[rootY] = rootX;
            cnt[rootX] += cnt[rootY];
            _cnt = cnt[rootX];
        } else {
            fa[rootX] = rootY;
            cnt[rootY] += cnt[rootX];
            _cnt = cnt[rootY]; 
        }
        
        return _cnt;
    }
private:
    unordered_map<int, int> mp, cnt, fa;
};

130. 被围绕的区域

找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。

class Solution {
public:
    vector<vector<int> > dir = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    void solve(vector<vector<char>>& board) {
        int n = board.size(), m = board[0].size();
        if(n==0 || m==0) 
            return;

        int dummy = m*n;
        for(int i = 0; i < n*m; i++) {
            fa[i] = i;
            sz[i] = 1;
        }
        
        // 将第一列和最后一列O与dummy合并
        for(int i = 0; i < n; i++) {
            if(board[i][0] == 'O') 
                merge(i*m, dummy);
            if(board[i][m-1] == 'O')
                merge(i*m+m-1, dummy);
        }

        // 将第一行和最后一行O与dummy合并
        for(int i = 0; i < m; i++) {
            if(board[0][i] == 'O')
                merge(i, dummy);
            if(board[n-1][i] == 'O')
                merge((n-1)*m+i, dummy);
        }

        for(int i = 1; i < n-1; i++) {
            for(int j = 1; j < m-1; j++) {
                if(board[i][j] == 'O') {
                    for(int k = 0; k < 4; k++) {
                        int x = i + dir[k][0];
                        int y = j + dir[k][1];
                        if(board[x][y] == 'O') {
                            merge(x*m+y, i*m+j);
                        }
                    }
                }
            }
        }

        for(int i = 1; i < n-1; i++) {
            for(int j = 1; j < m-1; j++) {
                if(!connected(i*m+j, dummy)) 
                    board[i][j] = 'X';
            }
        }     
    }

    void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if(rootX == rootY) 
            return;
        
        if(sz[rootX] > sz[rootY]) {
            fa[rootY] = rootX;
            sz[rootX] += sz[rootY];
        } else {
            fa[rootX] = rootY;
            sz[rootY] += sz[rootX];
        }
    }

    int find(int x) {
        while(fa[x] != x) {
            fa[x] = fa[fa[x]];
            x = fa[x];
        }

        return x;
    }

    bool connected(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        return rootX==rootY;
    }

private:
    unordered_map<int, int> fa, sz; 
};

200. 岛屿数量

你计算网格中岛屿的数量。

class Solution {
public:
    int find(int x) {
        while(fa[x] != x) {
            fa[x] = fa[fa[x]];
            x = fa[x];
        }
        
        return x;
    }
    
    void merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if(rootX == rootY) return;
        
        if(sz[rootX] > sz[rootY]) {
            fa[rootY] = rootX;
            sz[rootX] += sz[rootY];
        } else {
            fa[rootX] = rootY;
            sz[rootY] += sz[rootX];
        }
        cnt--;
    }
    
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                int idx  =i*m + j;
                fa[idx] = idx;
                sz[idx] = 1;
                
                if(grid[i][j] == '1')
                    cnt++;
            }
        }
        
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                if(grid[i][j] == '1') {
                    int idx = i*m + j;
                    if(i+1<n && grid[i+1][j]=='1') 
                        merge(idx, (i+1)*m+j);
                    
                    if(j+1<m && grid[i][j+1]=='1')
                        merge(idx, (i*m)+j+1);
                }
            }
        }
        
        return cnt;
    }
private:
    int cnt = 0;
    unordered_map<int, int> fa, sz;
};

547. 省份数量

给你一个 n x n 的矩阵 isConnected ，返回矩阵中 省份 的数量。

int findCircleNum(vector<vector<int>>& isConnected) {
        int m = isConnected.size();
        for(int i = 0; i < m; i++) {
            fa[i] = i;
            cnt[i] = 1;
        }
        
        int ans = m;
        for(int i = 0; i < m; i++) {
            for(int j = i+1; j < m; j++) {
                if(isConnected[i][j] && merge(i, j)) {
                    ans--;
                }
            }
        }
        
        return ans;
    }
    
    int find(int x) {
        while(x != fa[x]) {
            fa[x] = fa[fa[x]];
            x= fa[x];
        }
        
        return x;
    }
    
    bool merge(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if(rootX == rootY) {
            return false;
        }
        
        if(cnt[rootX] > cnt[rootY]) {
            fa[rootY] = rootX;
            cnt[rootX] += cnt[rootY];
        } else {
            fa[rootX] = rootY;
            cnt[rootY] += cnt[rootX];
        }
        
        return true;
    }
    
private:
    unordered_map<int, int> fa, cnt;
};

位我上者，灿烂星空；道德律令，在我心中。