题目地址：

https://leetcode.com/problems/making-a-large-island/

给定一个二维$0-1$矩阵，允许将其中的某一个$0$变为$1$，问能得到的最大的$1$连通块的面积（即$1$的数量）。

法1：并查集。这个问题的关键在于，当遍历到$0$的时候，将其变为$1$之后连通了其的四个邻居，但不知道这四个邻居是属于不同连通块的还是属于相同连通块的，如果属于相同连通块，就会造成重复计算的问题。这时候并查集可以解决这个问题，当两个节点在并查集的树的祖宗节点相等，就说明它们是属于同一个连通块的。这样就能避免重复计算。同时也需要注意矩阵全是$1$的情况，这时直接返回矩阵的面积即可。代码如下：

import java.util.*; public class Solution { class Pair { int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } @Override public boolean equals(Object o) { Pair pair = (Pair) o; return x == pair.x && y == pair.y; } @Override public int hashCode() { return Objects.hash(x, y); } } class UnionFind { Map<Pair, Pair> parent; Map<Pair, Integer> size; public UnionFind() { parent = new HashMap<>(); size = new HashMap<>(); } public void add(Pair x) { if (!parent.containsKey(x)) { parent.put(x, x); size.put(x, 1); } } // 找到x的祖宗节点 public Pair find(Pair x) { add(x); if (!x.equals(parent.get(x))) { parent.put(x, find(parent.get(x))); } return parent.get(x); } public void union(Pair x, Pair y) { Pair px = find(x), py = find(y); if (px.equals(py)) { return; } parent.put(px, py); size.put(py, size.get(px) + size.get(py)); } public int getSize(Pair x) { return size.get(find(x)); } } public int largestIsland(int[][] grid) { int m = grid.length, n = grid[0].length; UnionFind uf = new UnionFind(); for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { // 接下来将1连通块都union起来 if (grid[i][j] == 1) { Pair cur = new Pair(i, j); uf.add(cur); int[] d = {1, 0, -1, 0, 1}; for (int k = 0; k < 4; k++) { int nextI = i + d[k], nextJ = j + d[k + 1]; if (0 <= nextI && nextI < m && 0 <= nextJ && nextJ < n && grid[nextI][nextJ] == 1) { Pair next = new Pair(nextI, nextJ); uf.union(cur, next); } } } } } int res = 0; // 记录有没有找到0 boolean found = false; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 0) { found = true; Set<Pair> set = new HashSet<>(); int area = 1; int[] d = {1, 0, -1, 0, 1}; for (int k = 0; k < 4; k++) { int nextI = i + d[k], nextJ = j + d[k + 1]; if (0 <= nextI && nextI < m && 0 <= nextJ && nextJ < n && grid[nextI][nextJ] == 1) { Pair next = new Pair(nextI, nextJ); // 找到邻居的祖宗，相同祖宗的邻居的1连通块面积只算1次 Pair ancestor = uf.find(next); if (!set.contains(ancestor)) { area += uf.getSize(ancestor); set.add(ancestor); } } } res = Math.max(res, area); } } } return found ? res : m * n; } }

时间复杂度$O(mn{\log }^{\ast }(mn))$，空间$O(mn)$。

注解：这个方法虽然容易想到，但哈希表的put非常耗时。数组并查集的版本可以参考https://blog.csdn.net/qq_46105170/article/details/109178762。

法2：BFS + 标记连通块编号。思路是将每个$1$连通块编上号，并且用哈希表存一下每个编号对应的$1$连通块的面积。这样只需要保证相同编号的$1$连通块的面积不要累加两次就行了。标记$1$连通块的过程可以用BFS来实现（当然DFS也可以，参考https://blog.csdn.net/qq_46105170/article/details/109178762）。代码如下：

import java.util.*; public class Solution { public int largestIsland(int[][] grid) { int m = grid.length, n = grid[0].length; int[][] ids = new int[m][n]; boolean[][] visited = new boolean[m][n]; // 存编号为key的1连通块的面积 Map<Integer, Integer> map = new HashMap<>(); for (int i = 0, id = 1; i < m; i++) { for (int j = 0; j < n; j++) { if (!visited[i][j] && grid[i][j] == 1) { map.put(id, bfs(i, j, id, ids, grid, visited)); id++; } } } int res = 0; boolean found = false; int[] d = {1, 0, -1, 0, 1}; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 0) { found = true; int area = 1; Set<Integer> set = new HashSet<>(); for (int k = 0; k < 4; k++) { int nextI = i + d[k], nextJ = j + d[k + 1]; if (inBound(nextI, nextJ, grid) && grid[nextI][nextJ] == 1) { int id = ids[nextI][nextJ]; // 相同id的连通块面积只累加一次 if (!set.contains(id)) { area += map.get(id); set.add(id); } } } res = Math.max(res, area); } } } return found ? res : m * n; } // 对(x, y)所在的1连通块做BFS，返回其面积，同时将该连通块的编号填充为id private int bfs(int x, int y, int id, int[][] ids, int[][] grid, boolean[][] visited) { visited[x][y] = true; ids[x][y] = id; int area = 0; Queue<int[]> queue = new LinkedList<>(); queue.offer(new int[]{x, y}); int[] d = {1, 0, -1, 0, 1}; while (!queue.isEmpty()) { area++; int[] cur = queue.poll(); for (int i = 0; i < 4; i++) { int nextX = cur[0] + d[i], nextY = cur[1] + d[i + 1]; if (inBound(nextX, nextY, grid) && grid[nextX][nextY] == 1 && !visited[nextX][nextY]) { // 填充id ids[nextX][nextY] = id; visited[nextX][nextY] = true; queue.offer(new int[]{nextX, nextY}); } } } return area; } private boolean inBound(int x, int y, int[][] grid) { return 0 <= x && x < grid.length && 0 <= y && y < grid[0].length; } }

时空复杂度$O(mn)$。