827. 最大人工岛
关键词：深度优先、并查集、枚举
题目起源：827. 最大人工岛 - 力扣（Leetcode）
题目形容
T深度优先 T并查集 T枚举给你一个大小为 n x n 二进制矩阵 grid 。最多 只能将一格 0 变成 1 。
返回执行此操作后，grid 中最大的岛屿面积是多少？
岛屿 由一组上、下、左、右四个方向相连的 1 造成。
输出: grid = [[1, 0], [0, 1]]输入: 3解释: 将一格0变成1，最终连通两个小岛失去面积为 3 的岛屿。输出: grid = [[1, 1], [1, 0]]输入: 4解释: 将一格0变成1，岛屿的面积扩充为 4。输出: grid = [[1, 1], [1, 1]]输入: 4解释: 没有0能够让咱们变成1，面积仍然为 4。数据范畴n == grid.lengthn == grid[i].length1 <= n <= 500grid[i][j] 为 0 或 1问题剖析
连通块问题可应用深搜来打标记，也能够应用并查集来保护，以下就采纳并查集来解决本题。
首先遍历一遍矩阵，当相邻两格均为岛屿时，认为二者连通，用并查集来保护二者的连通性。
枚举每一个网格的翻转（前提是能翻转），将其退出图中，其是否能使得其上下左右的连通块（或其中几个）相连，留神相似于上方连通块与左方连通块原本就相连的状况。
工夫复杂度：O(n^2)，find函数的工夫可认为是O(1)的。
空间复杂度：O(n^2)
代码实现
const int N = 25e4 + 5;int p[N], size[N], n;int find(int x) { if (p[x] != x)p[x] = find(p[x]); return p[x];}/** * 将二维坐标映射到一维 */int pos(int x, int y) { return x * n + y;}int largestIsland(vector<vector<int>> &grid) { n = grid.size(); // 并查集初始化 for (int i = 0, k = n * n; i < k; i++) { p[i] = i, size[i] = 1; } // 后果 int res = grid[0][0]; // 当n为1时的非凡状况 // 独自解决第一行和第一列 for (int i = 1, pa, pb; i < n; i++) { if (grid[0][i] && grid[0][i - 1]) { pa = find(pos(0, i)), pb = find(pos(0, i - 1)); p[pa] = pb, size[pb] += size[pa]; res = max(size[pb], res); // 单个连通块最大值 } if (grid[i][0] && grid[i - 1][0]) { pa = find(pos(i, 0)), pb = find(pos(i - 1, 0)); p[pa] = pb, size[pb] += size[pa]; res = max(size[pb], res); // 单个连通块最大值 } } // 处于其余块的连通性 for (int i = 1, pa, pb; i < n; i++) { for (int j = 1; j < n; j++) { if (!grid[i][j])continue; pa = find(pos(i, j)); if (grid[i - 1][j]) { pb = find(pos(i - 1, j)); if (pa != pb) { p[pb] = pa, size[pa] += size[pb]; } } if (grid[i][j - 1]) { pb = find(pos(i, j - 1)); if (pa != pb) { p[pb] = pa, size[pa] += size[pb]; } } res = max(size[pa], res); // 单个连通块最大值 } } // 枚举每个翻转 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (grid[i][j])continue; // 以后网格连同上下左右连通块的和 int tp = 1; // 上下左右四个方向的连通块的根节点（代表结点） int up = -1, dn = -1, lt = -1, rt = -1; if (i - 1 >= 0 && grid[i - 1][j]) { up = find(pos(i - 1, j)); // 记录上方连通块的根节点 tp += size[up]; // 累加上方连通块的大小 } if (i + 1 < n && grid[i + 1][j]) { dn = find(pos(i + 1, j)); if (dn != up) { // 下方连通块不与上方连通块连通 tp += size[dn]; } } if (j - 1 >= 0 && grid[i][j - 1]) { lt = find(pos(i, j - 1)); if (lt != up && lt != dn) { // 左侧连通块不与上、下方连通块连通 tp += size[lt]; } } if (j + 1 < n && grid[i][j + 1]) { rt = find(pos(i, j + 1)); if (rt != up && rt != dn && rt != lt) { // 右侧连通块不与上、下、左方连通块连通 tp += size[rt]; } } // 取最大值 res = max(tp, res); } } return res;}