date: 2020/02/07


基本概念

并查集是一种数据结构,它管理一系列不相交的动态集合,主要用于判断两个元素是否同属于一个集合,并且可以便捷地合并两个集合。每个集合选取其中一个元素作为代表,这个代表无关紧要,选谁都行。

class UnionFind{
private:
    vector<int> parents;
    vector<int> rank;   // for union with optimization
public:
    UnionFind(int num){
        for(int i = 0; i < num; i++)
            parents.push_back(i);
        rank.assign(num, 0);
    }
    
    /* // without optimization
    // 空间O(1)时间O(r),r为秩
    int find(int x){
        if(parents[x] != x)
            return origin_find(parents[x]);
        return x;
    }
    // 空间O(1)时间O(r)
    void merge(int a, int b){
        a = find(a);
        b = find(b);
        parents[b] = a;
    }
    */
    
    // 空间O(1),时间最好O(1)最坏O(r)摊还O(1)
    int find(int x){
        if(parents[x] != x)
            parents[x] = find(parents[x]);
        return parents[x];
    }    
    
    // 空间O(1),时间最好O(1)最坏O(r)摊还O(1)
    void merge(int a, int b){
        a = find(a);
        b = find(b);
        if(a == b) return;
        
        if(rank[a] < rank[b]){
            parents[a] = b;
        }else if(rank[a] > rank[b]){
            parents[b] = a;
        }else{  // rank[a] == rank[b]
            parents[a] = b; rank[b]++;
            // or parents[b] = a; rank[a]++;
        }
    }
};


200岛屿数量(中等)

https://leetcode-cn.com/problems/number-of-islands

注意四个方向都需要搜索,别光向右会向下搜索(万一岛屿上有湖呢)

void helper(vector<vector<char>>& grid, int x, int y){
    int nx = grid.size(), ny = grid[0].size();
    grid[x][y] = '0';
    if(x - 1 >= 0 && grid[x-1][y] == '1')
        helper(grid, x-1, y);
    if(x + 1 < nx && grid[x+1][y] == '1')
        helper(grid, x+1, y);
    if(y - 1 >= 0 && grid[x][y-1] == '1')
        helper(grid, x, y-1);
    if(y + 1 < ny && grid[x][y+1] == '1')
        helper(grid, x, y+1);
}

int numIslands(vector<vector<char>>& grid) {
    if(grid.size() == 0 || grid[0].size() == 0)
        return 0;
    int nx = grid.size(), ny = grid[0].size();
    int counter = 0;
    for(int i = 0; i < nx; i++){
        for(int j = 0; j < ny; j++){
            if(grid[i][j] == '1'){
                helper(grid, i, j);
                counter++;
            }
        }
    }
    return counter;
}
int numIslands(vector<vector<char>>& grid) {
    if(grid.size() == 0 || grid[0].size() == 0)
        return 0;
    int nx = grid.size(), ny = grid[0].size();
    int counter = 0;
    queue<pair<int, int>> next;
    for(int x= 0; x < nx; x++){
        for(int y = 0; y < ny; y++){
            if(grid[x][y] == '1'){
                counter++;
                next.push(make_pair(x, y));
                grid[x][y] = '0';   // 别等出队的时候再“淹没”
                while(!next.empty()){
                    int cx = next.front().first, cy = next.front().second;
                    next.pop();
                    if(cx - 1 >= 0 && grid[cx-1][cy] == '1'){
                        next.push(make_pair(cx-1, cy));
                        grid[cx-1][cy] = '0';   // 别等出队的时候再“淹没”
                    }
                    if(cx + 1 < nx && grid[cx+1][cy] == '1'){
                        next.push(make_pair(cx+1, cy));
                        grid[cx+1][cy] = '0';   // 别等出队的时候再“淹没”
                    }
                    if(cy - 1 >= 0 && grid[cx][cy-1] == '1'){
                        next.push(make_pair(cx, cy-1));
                        grid[cx][cy-1] = '0';   // 别等出队的时候再“淹没”
                    }
                    if(cy + 1 < ny && grid[cx][cy+1] == '1'){
                        next.push(make_pair(cx, cy+1));
                        grid[cx][cy+1] = '0';   // 别等出队的时候再“淹没”
                    }
                }
            }
        }
    }
    return counter;
}

逐一跟相邻大陆合并,最后统计剩下的大陆数量

// 省略并查集的定义
// 与上边基础概念里的定义类似,额外需要
// 1. 在构造的时候接受grid初始化一个nx*ny大小的parents和rank
// 2. 维护一个count,统计陆地的数量(初始状态下为grid中1的个数)
// 3. 提供一个访问count成员的get_count接口

int numIslands(vector<vector<char>>& grid) {
    if(grid.size() == 0 || grid[0].size() == 0)
        return 0;
    int nx = grid.size(), ny = grid[0].size();
    UnionFind uf(grid);
    for(int x = 0; x < nx; x++){
        for(int y = 0; y < ny; y++){
            if(grid[x][y] == '1'){
                grid[x][y] = '0';
                if(x - 1 >= 0 && grid[x-1][y] == '1')
                    uf.merge(x * ny + y, (x-1) * ny + y);
                if(x + 1 < nx && grid[x+1][y] == '1')
                    uf.merge(x * ny + y, (x+1) * ny + y);
                if(y - 1 >= 0 && grid[x][y-1] == '1')
                    uf.merge(x * ny + y, x * ny + (y-1));
                if(y + 1 < ny && grid[x][y+1] == '1')
                    uf.merge(x * ny + y, x * ny + (y+1));
            }
        }
    }
    return uf.get_count();
}


547朋友圈(中等)

https://leetcode-cn.com/problems/friend-circles

200岛屿数量 一模一样,懒得做了