用并查集解决岛屿问题

并查集算法优美，结构简单，适用于各种图论的连接问题，缺点就是时间复杂度高，但是比DFS和BFS好理解一些，遇到算法问题易于快速上手。

并查集主要有三个函数：初始化、查找和合并。

初始化

int fa[MAXN];
inline void init(int n)
{
    for (int i = 1; i <= n; ++i)
        fa[i] = i;
}

假如有编号为1, 2, 3, …, n的n个元素，我们用一个数组fa[]来存储每个元素的父节点（因为每个元素有且只有一个父节点，所以这是可行的）。一开始，我们先将它们的父节点设为自己。

查询

int find(int x)
{
    if(fa[x] == x)
        return x;
    else
        return find(fa[x]);
}

我们用递归的写法实现对代表元素的查询：一层一层访问父节点，直至根节点（根节点的标志就是父节点是本身）。要判断两个元素是否属于同一个集合，只需要看它们的根节点是否相同即可。

合并

inline void merge(int i, int j)
{
    fa[find(i)] = find(j);
}

合并操作也是很简单的，先找到两个集合的代表元素，然后将前者的父节点设为后者即可。当然也可以将后者的父节点设为前者，这里暂时不重要。本文末尾会给出一个更合理的比较方法。

• 一般会使用一维的fa数组保存节点的根节点，因为这样方便find(int x)的递归查找。所以即使岛屿问题是二维的，也先转化为一维节点数组处理。

岛屿数量问题（LC200）

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。

示例 1：

输入：grid = [
[“1”,“1”,“1”,“1”,“0”],
[“1”,“1”,“0”,“1”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“0”,“0”,“0”]
]
输出：1
示例 2：

输入：grid = [
[“1”,“1”,“0”,“0”,“0”],
[“1”,“1”,“0”,“0”,“0”],
[“0”,“0”,“1”,“0”,“0”],
[“0”,“0”,“0”,“1”,“1”]
]
输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j]的值为 ‘0’ 或 ‘1’

这道题用DFS和BFS当然可以解决，但是难想。如果考虑并查集，思路很清晰，只需要遍历每个点，找到属性相同的点并让他们的根节点相同，最后从这些根节点里找到属于“1”的位置，即为岛屿。需要注意的是，第一次遍历找出来的根节点也不一定是最终的根节点，根节点也可能指向新的根节点，这时需要再用find(x)找到最厉害的那个根节点。

class Solution {
    public int numIslands(char[][] grid) {
        int M = grid.length;
        int N = grid[0].length;
        int[] fa = new int[M * N];
        init(grid, fa);
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                int num = i * N + j;
                if (j > 0 && grid[i][j] == grid[i][j - 1]) union(num, num - 1, fa);
                if (i > 0 && grid[i][j] == grid[i - 1][j]) union(num, num - N, fa);
            }
        }
        Set<Integer> integers = new HashSet<>();
        for (Integer item : fa) {
            integers.add(find(item, fa));//这里注意
        }
        int count = 0;
        for (Integer integer : integers) {
            if (grid[integer / N][integer % N] == '1') count++;
        }
        return count;
    }

    public void init(char[][] grid, int[] fa) {
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                fa[i * grid[0].length + j] = i * grid[0].length + j;
            }
        }
    }

    public int find(int x, int[] fa) {
        return x == fa[x] ? x : (fa[x] = find(fa[x], fa));
    }

    public void union(int x, int y, int[] fa) {
        int m = find(x, fa);
        int n = find(y, fa);
        fa[m] = fa[n];
    }
}

如图，fa中(0,0)为2，(1,0)、(2,0)等都是(0,0)的小弟，但是(0,0)是(0,2)的小弟（他本来是0，但是后面被改了），这时真正的大佬为(0,2)。1、8带入原grid得到的是水，0、2得到的是岛，但是0是2的子节点，因此只有一个岛。