[Python3] union-find
\n\nclass UnionFind:\n    def __init__(self, n): \n        self.parent = list(range(n))\n        self.rank = [1] * n \n        \n    def find(self, p): \n      
\n```\nclass UnionFind:\n    def __init__(self, n): \n        self.parent = list(range(n))\n        self.rank = [1] * n \n        \n    def find(self, p): \n        if self.parent[p] != p: \n            self.parent[p] = self.find(self.parent[p])\n        return self.parent[p]\n    \n    def union(self, p, q): \n        prt, qrt = self.find(p), self.find(q)\n        if prt == qrt: return False \n        if self.rank[prt] > self.rank[qrt]: prt, qrt = qrt, prt\n        self.parent[prt] = qrt\n        self.rank[qrt] += self.rank[prt] \n        return True \n    \n\nclass Solution:\n    def largestIsland(self, grid: List[List[int]]) -> int:\n        n = len(grid) # dimension \n        uf = UnionFind(n*n)\n        for i in range(n):\n            for j in range(n): \n                if grid[i][j]: \n                    for (ii, jj) in (i-1, j), (i, j-1): \n                        if 0 <= ii < n and 0 <= jj < n and grid[ii][jj]: uf.union(i*n+j, ii*n+jj)\n        \n        freq = defaultdict(int)\n        for i in range(n*n): freq[uf.find(i)] += 1\n        \n        ans = 0 \n        for i in range(n): \n            for j in range(n): \n                if grid[i][j]: ans = max(ans, freq[uf.find(i*n+j)])\n                else: \n                    cand = 1\n                    seen = set()\n                    for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j): \n                        if 0 <= ii < n and 0 <= jj < n: \n                            if grid[ii][jj]: \n                                key = uf.find(ii*n + jj)\n                                if key not in seen: \n                                    seen.add(key)\n                                    cand += freq[key]\n                    ans = max(ans, cand)\n        return ans \n```\n\n\n```\nclass Solution:\n    def largestIsland(self, grid: List[List[int]]) -> int:\n        n = len(grid) \n        v = 2 \n        freq = defaultdict(int)\n        for r in range(n): \n            for c in range(n): \n                if grid[r][c] == 1: \n                    stack = [(r, c)]\n                    grid[r][c] = v\n                    while stack: \n                        i, j = stack.pop()\n                        freq[v] += 1\n                        for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j): \n                            if 0 <= ii < n and 0 <= jj < n and grid[ii][jj] == 1: \n                                stack.append((ii, jj))\n                                grid[ii][jj] = v\n                    v += 1\n                    \n        ans = max(freq.values(), default=0)\n        for i in range(n): \n            for j in range(n): \n                if grid[i][j] == 0: \n                    cand = 1\n                    seen = set()\n                    for ii, jj in (i-1, j), (i, j-1), (i, j+1), (i+1, j): \n                        if 0 <= ii < n and 0 <= jj < n and grid[ii][jj] and grid[ii][jj] not in seen: \n                            seen.add(grid[ii][jj])\n                            cand += freq[grid[ii][jj]]\n                    ans = max(ans, cand)\n        return ans \n```
['Python3']