【图, 并查集】岛屿数量

题目

200. 岛屿数量

---

给你一个由 '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'

解题

方法一：并查集

思路

与 [【图, 并查集】岛屿数量 II.md](【图, 并查集】岛屿数量 II.md) 的解法差不多，只不过这次提前给了二维网格中每个格子的状态。

代码

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n + 1);
        for (int[] edge : edges) {
            if (uf.isConnected(edge[0], edge[1])) return edge;
            uf.union(edge[0], edge[1]);
        }
        return new int[2];
    }

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

        public UnionFind() {}

        public UnionFind(int size) {
            groups = size;
            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]++;
            }
            groups--;
        }

        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);
        }
    }
}

优化

既然每个格子状态都知道，就不用上下左右全部检查一遍了，只要检查右边和下边或者左边和上边，能覆盖所有格子就行。

class Solution {
    public int numIslands(char[][] grid) {
        int rowLen = grid.length, colLen = grid[0].length;
        UnionFind uf = new UnionFind(rowLen * colLen);
        for (int row = 0; row < rowLen; row++) {
            for (int col = 0; col < colLen; col++) {
                if (grid[row][col] == '0') continue;
                int idx = row * colLen + col;
                uf.count++;
                if (row - 1 >= 0 && grid[row - 1][col] == '1') {
                    uf.union(idx, (row - 1) * colLen + col);
                }
                if (col + 1 < colLen && grid[row][col + 1] == '1') {
                    uf.union(idx, idx + 1);
                }
            }
        }
        return uf.count;
    }

    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);
        }
    }
}