用并查集解决「岛屿最大面积问题」

想要实现并查集，首先要先理解和实现两个最基本的函数 Find(int x)、Union(int x, int y)

• Find(int x) 实现的功能是查找 x 是属于哪一个集合；
• Union(int x, int y) 是将 x 和 y 弄成同一个集合；

数组 parent 是记录每个元素与哪一个元素属于同一个集合。当用 Find(x) 寻找的时候，如果 parent[x] == x 则证明当前元素是根元素，否则继续寻找 parent[x] 的根元素；

数组 rank 用来记录根元素所属于的集合中具有多少个元素，只有属于根元素位置上的数字有意义；

class UnionFind {
public:
    UnionFind(n) {
        count = n;
        parent = vector<int>(n);
        rank = vector<int>(n, 1);
        for (int i = 0; i < parent.size(); i++) {
            parent[i] = i;
        }
    }
    
    int Find(int x) {
        // 寻找元素 x 的根元素
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
    
    void Union(int x, int y) {
        int root_x = Find(x);
        int root_y = Find(y);
        if (root_x == root_y) { return; }
        if (rank[root_x] >= rank[root_y]) {
            parent[root_y] = root_x;
            rank[root_x] += rank[root_y];
        } else {
            parent[root_x] = root_y;
            rank[root_y] += rank[root_x];
        }
        count--;  // 让连接了一个, 让集合数减一
    }
    
private:
    int count;
    vector<int> parent;
    vector<int> rank;
}

用并查集解决岛屿最大面积问题

问题描述：

【题目】剑指 Offer II 105. 岛屿的最大面积：给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

// 首先把并查集类写出来
// 问题中的 grid 是一个二维的 vector, 并查集中用一维 vector 来处理
// 行数为 m, 列数为 n, grid[i][j] 对应在并查集中的位置就是 [i * n + j]
class UnionFind {
public: 
    // 构造函数
    UnionFind(int n) {
        count = n;  // 总共集合总数
        parent = vector<int>(n);
        rank = vector<int>(n);
        for (int i = 0; i < parent.size(); i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }
    
    // 返回根元素
    int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
    
    // 将 x 和 y 进行合并
    void Union(int x, int y) {
        int root_x = Find(x);
        int root_y = Find(y);
        // 如果 x, y 已经属于同一个集合则不用继续操作, 直接返回
        if (root_x == root_y) { return; }
        // 让元素比较少的集合变成元素比较多的集合, 这样之后的修改会更省事
        if (rank[root_x] >= rank[root_y]) {
            parent[root_y] = root_x;
            rank[root_x] += rank[root_y];
        } else {
            parent[root_x] = root_y;
            rank[root_y] += rank[root_x];
        }
        count--;  // 集合总数减 1
    }

    // 返回 rank 数组
    vector<int> get_rank() {
        return rank;
    }
    
    // 返回 parent 数组
    vector<int> get_parent() {
        return parent;
    }

private:
    vector<int> parent;
    vector<int> rank;
    int count;
};

class Solution {
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int dx[4] = {-1, 1, 0, 0};
        int dy[4] = {0, 0, -1, 1};
        int m = grid.size();
        if (m == 0) { return 0; }
        int n = grid[0].size();
        UnionFind uf = UnionFind(m * n);

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; k++) {
                        int x = i + dx[k];
                        int y = j + dy[k];
                        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                            uf.Union(i * n + j, x * n + y);
                        }
                    }
                }
            }
        }
        
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    ans = max(ans, uf.get_rank()[i * n + j]);
                }
            }
        }
        return ans;
    }
};

用并查集解决这个问题时间花费会比 DFS 和 BFS 更大，但是最主要的还是学习并查集的思想以及如何实现。