1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157
 class Solution { public: vector<int> leader; vector<int> total; int largestIsland(vector<vector<int>>& grid) { int row = grid.size(), col = grid[0].size(); int size = row * col; leader.resize(size); total.resize(size, 1); for (int i = 0; i < size; i++) { leader[i] = i; } vector<vector<int>> dirs = {{0, 1}, {1, 0}, {0, 1}, {1, 0}}; for (int r = 0; r < row; r++) { for (int c = 0; c < col; c++) { if (grid[r][c] == 1) { for (auto d : dirs) { int rr = r + d[0]; int cc = c + d[1]; if (rr < 0  rr >= row  cc < 0  cc >= col  grid[rr][cc] == 0) continue; Union(find(r*row + c), find(rr*row + cc)); } } } } int max_island = 0; for (int r = 0; r < row; r++) { for (int c = 0; c < col; c++) { if (grid[r][c] == 0) { unordered_set<int> set; for (auto d : dirs) { int rr = r + d[0]; int cc = c + d[1]; if (rr < 0  rr >= row  cc < 0  cc >= col  grid[rr][cc] == 0) continue; set.insert(find(rr * row + cc)); } int cnt = 1; for (auto i : set) cnt += total[i]; max_island = max(max_island, cnt); } } } return max_island == 0 ? size : max_island; } int find(int i) { if (leader[i] != i) leader[i] = find(leader[i]); return leader[i]; } void Union(int i, int j) { int x = leader[i]; int y = leader[j]; if (x == y) return; leader[x] = y; total[y] += total[x]; } };
class Solution2 { public: int largestIsland(vector<vector<int>>& grid) { int row = grid.size(), col = grid[0].size();
vector<vector<bool>> seen(row, vector<bool>(col, false)); vector<vector<int>> ids(row, vector<int>(col)); unordered_map<int, int> maps; int max_islands = 0;
int id = 0;
for (int r = 0; r < row; r++) { for (int c = 0; c < row; c++) { if (grid[r][c] == 0  seen[r][c] == true) continue;
int total = 0; dfs(grid, r, c, seen, total, ids, id); maps[id] = total; max_islands = max(max_islands, total); id++; } }
vector<vector<int>> dirs = {{0,1}, {1,0}, {1,0}, {0,1}};
for (int r = 0; r < row; r++) { for (int c = 0; c < row; c++) { if (grid[r][c] == 0) { unordered_set<int> sets;
for (auto &dir : dirs) { int x = r + dir[0]; int y = c + dir[1];
if (x < 0  x >= row  y < 0  y >= col  grid[x][y] == 0) continue;
int id = ids[x][y]; sets.insert(id); }
int islands = 1; for (int id : sets) islands += maps[id];
max_islands = max(max_islands, islands); } } }
return max_islands; }
void dfs(vector<vector<int>>& grid, int r, int c, vector<vector<bool>> &seen, int &total, vector<vector<int>> &ids, int id) {
int row = grid.size(), col = grid[0].size();
vector<vector<int>> dirs = {{0,1}, {1,0}, {1,0}, {0,1}};
seen[r][c] = true; total++; ids[r][c] = id;
for (auto &dir : dirs) { int x = r + dir[0]; int y = c + dir[1];
if (x < 0  x >= row  y < 0  y >= col  grid[x][y] == 0  seen[x][y] == true) continue;
dfs(grid, x, y, seen, total, ids, id); } } };
