[Python] dfs with connected components, explained
What we need to do is to find all islands first (very similar to 0694 Number of Distinct Islands), we can do it in place: for each island we rewrite it with its
What we need to do is to find all islands first (very similar to **0694** Number of Distinct Islands), we can do it in place: for each island we rewrite it with its number (we start enumerate from `2`, because `0` and `1` already reserved), also we evaluate size of each island in `island` Counter. Then we need to traverse our grid once again and for each empty cell check four neighbors: and create set off all unique islands (it can happen that for example left neighbor and upper neighbor are the same island). Then we evaluate sum of sizes of all neighbours and choose the biggest one.\n\n#### Complexity\nTime complexity is `O(n*m)`, because we traverse our graph twice: one with `dfs` and another when we were looking for empty cells. Space complxity is potentially `O(n*m)` as well.\n\n#### Code\n```python\nclass Solution:\n    def largestIsland(self, grid):\n        m, n = len(grid), len(grid[0])\n        neib_list = [[1,0],[-1,0],[0,-1],[0,1]]\n        islands, count, ans = Counter(), 2, 0\n        \n        def dfs(t, i, j):\n            if not 0 <= i < m or not 0 <= j < n or grid[i][j] != 1: return\n            islands[t] += 1\n            grid[i][j] = t\n            for x, y in neib_list: dfs(t, x+i, y+j)\n                \n        for x, y in product(range(m), range(n)):\n            if grid[x][y] == 1:\n                dfs(count, x, y)\n                count += 1\n                \n        for x, y in product(range(m), range(n)):\n            if grid[x][y] != 0: continue\n            neibs = set()\n            for dx, dy in neib_list:\n                if 0 <= x + dx < m and 0 <= y + dy < n and grid[x+dx][y+dy] != 0:\n                    neibs.add(grid[x+dx][y+dy])\n            ans = max(ans, sum(islands[i] for i in neibs) + 1)\n            \n        return ans if ans != 0 else m*n\n```
['Depth-First Search']