【图, 并查集】岛屿数量 II

题目

305. 岛屿数量 II

---

给你一个大小为 m x n 的二进制网格 grid 。网格表示一个地图，其中，0 表示水，1 表示陆地。最初，grid 中的所有单元格都是水单元格（即，所有单元格都是 0）。

可以通过执行 addLand 操作，将某个位置的水转换成陆地。给你一个数组 positions ，其中 positions[i] = [ri, ci] 是要执行第 i 次操作的位置 (ri, ci) 。

返回一个整数数组 answer ，其中 answer[i] 是将单元格 (ri, ci) 转换为陆地后，地图中岛屿的数量。

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

示例 1：

输入：m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
输出：[1,1,2,3]
解释：
起初，二维网格 `grid` 被全部注入「水」。（0 代表「水」，1 代表「陆地」）
- 操作 #1：`addLand(0, 0)` 将 `grid[0][0]` 的水变为陆地。此时存在 1 个岛屿。
- 操作 #2：`addLand(0, 1)` 将 `grid[0][1]` 的水变为陆地。此时存在 1 个岛屿。
- 操作 #3：`addLand(1, 2)` 将 `grid[1][2]` 的水变为陆地。此时存在 2 个岛屿。
- 操作 #4：`addLand(2, 1)` 将 `grid[2][1]` 的水变为陆地。此时存在 3 个岛屿。

示例 2：

输入：m = 1, n = 1, positions = [[0,0]]
输出：[1]

提示：

• 1 <= m, n, positions.length <= 10^4
• 1 <= m * n <= 10^4
• positions[i].length == 2
• 0 <= ri < m
• 0 <= ci < n

进阶：你可以设计一个时间复杂度 O(k log(mn)) 的算法解决此问题吗？（其中 k == positions.length）

解题

方法一：并查集

思路

把二维的网格图当做一个无向图，横向或者纵向相邻的顶点之间有一条无向边，那么问题就变成了每次 addLand 操作之后在图中寻找连通分量的问题。

对于每个 addLand 操作。需要注意的逻辑是：

• 如果 addLand 操作的顶点已经访问过，跳过；
• 如果 addLand 操作的顶点没有访问过，此时需要增加连通分量个数，然后再将它与「上」「下」「左」「右」合并。

代码

class Solution {
    private static final int[][] DIRECTIONS = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        int size = m * n;
        UnionFind uf = new UnionFind(size);
        boolean[] visited = new boolean[size];
        List<Integer> ans = new ArrayList<>();
        for (int[] pos : positions) {
            int row = pos[0], col = pos[1];
            int idx = row * n + col;
            if (!visited[idx]) {
                uf.count++; // // 把水变成陆地，连通分量个数加 1
                visited[idx] = true;
                for (int[] direction : DIRECTIONS) {
                    int newRow = row + direction[0];
                    if (newRow < 0 || newRow >= m) continue;
                    int newCol = col + direction[1];
                    if (newCol < 0 || newCol >= n) continue;
                    int newIdx = newRow * n + newCol;
                    if (visited[newIdx]) uf.union(idx, newIdx);
                }
            }
            ans.add(uf.count);
        }
        return ans;
    }

    static class UnionFind {
        public int count;
        private int[] root;
        private int[] rank;

        public UnionFind() {}
        
        public UnionFind(int size) {
            count = 0;
            root = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                root[i] = i;
                rank[i] = 1;
            }
        }

        public void union(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP == rootQ) return;
            if (rank[rootP] > rank[rootQ]) {
                root[rootQ] = rootP;
            } else if (rank[rootP] < rank[rootQ]) {
                root[rootP] = rootQ;
            } else {
                root[rootQ] = rootP;
                rank[rootP]++;
            }
            count--;
        }
        
        public int find(int n) {
            return n == root[n] ? n : (root[n] = find(root[n]));
        }
        
        public boolean isConnected(int p, int q) {
            return find(p) == find(q);
        }
    }
}