305. 岛屿数量 II
假设你设计一个游戏，用一个 m 行 n 列的 2D 网格来存储你的游戏地图。

起始的时候，每个格子的地形都被默认标记为「水」。我们可以通过使用 addLand 进行操作，将位置 (row, col) 的「水」变成「陆地」。

你将会被给定一个列表，来记录所有需要被操作的位置，然后你需要返回计算出来 每次 addLand 操作后岛屿的数量。

注意：一个岛的定义是被「水」包围的「陆地」，通过水平方向或者垂直方向上相邻的陆地连接而成。你可以假设地图网格的四边均被无边无际的「水」所包围。

请仔细阅读下方示例与解析，更加深入了解岛屿的判定。

示例:

输入: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
输出: [1,1,2,3]

解析

我们可以简单解法，添加一次就重新计算一次岛屿数量，也就是 N*numsIsland() 。

这样就解决了问题，但是涉及到很多重复计算，所以我们使用并查集来解决此问题。

解法一

执行N次 numsIsland()，注意要用那种visited[]数组的方式，每一次都要初始化值

解法二

并查集，因为是动态添加，我们每增加一个陆地就对count+1，然后对于当前点的上下左右四个点进行union()，将所得的count重新赋值给总count，这时候得到的就是我们所要求的count

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        int[] parent = new int[m * n];
        //起初，所有的位置都是 水 ，所以他们的父亲节点置为 -1
        Arrays.fill(parent, -1);
        List<Integer> list = new ArrayList<>();
        int count = 0;
        for (int[] position : positions) {
            //i表示当前位置的陆地对应的节点的id
            int i = position[0] * n + position[1];
            //判断该位置是否已经成为了陆地，排除positions中的重复的陆地位置
            if (parent[i] != -1) {
                list.add(count);
                continue;
            }
            //若之前时水，现在添加为陆地，则它的父亲节点置为它自己，并且岛屿数量加1
            parent[i] = i;
            count++;
            //对该位置的上下左右四个位置进行并查集的合并
            //如果上下左右是陆地，则进行集合的合并，反之则跳过
            //合并路径的时候，需要判断这两个位置是否已经在一个集合中了
            //如果两个位置的陆地已经在同一个集合中了，则跳过
            //反之，则合并集合，并且岛屿数量-1
            if (position[0] > 0 && parent[i - n] != -1) {
                count = union(i, i - n, parent, count);
            }
            if (position[0] < m - 1 && parent[i + n] != -1) {
                count = union(i, i + n, parent, count);
            }
            if (position[1] > 0 && parent[i - 1] != -1) {
                count = union(i, i - 1, parent, count);
            }
            if (position[1] < n - 1 && parent[i + 1] != -1) {
                count = union(i, i + 1, parent, count);
            }
            list.add(count);
        }
        return list;
    }

    public int union(int i, int j, int[] parent, int count) {
        int parent_1 = find(i, parent);
        int parent_2 = find(j, parent);
        //判断这两个位置是否已经在同一个集合中
        //如果两个位置已经在同一个集合中了，则跳过
        //反之，则合并集合，并且岛屿数量-1
        if (parent_1 != parent_2) {
            count--;
            parent[parent_2] = parent_1;
        }
        return count;
    }

    public int find(int i, int[] parent) {
        //路径优化
        if (parent[i] != i) {
            parent[i] = find(parent[i], parent);
        }
        return parent[i];
    }
}

注意：本文归作者所有，未经作者允许，不得转载