Python || DFS || Connect components
Intuition\nDFS and components.\n\n# Approach\nCreate seperate components consisting of all islands and mark all elements of every component with a unique id whi
# Intuition\nDFS and components.\n\n# Approach\nCreate seperate components consisting of all islands and mark all elements of every component with a unique id which is >1 to avoid confusion.Now map that id to the area of that component(no of ones in it).\nNow again traverse the grid and whenever you see a 0, try to check unique components in its 4 directions and add areas of all of them and update max value.\nIf there is no 0 in grid simply return m*n.\n\n# Complexity\n- Time complexity:\nO(m*n) [2 pass]\n\n- Space complexity:\nO(1)\n\n# Code\n```\nclass Solution:\n    def largestIsland(self, grid: List[List[int]]) -> int:\n        m,n=len(grid),len(grid[0])\n        mp={}\n        mmax=0\n        directions=((0,1),(1,0),(0,-1),(-1,0))\n        def solve(i,j):\n            ans=1\n            seen=set()\n            for di,dj in directions:\n                ni,nj=i+di,j+dj\n                if 0<=ni<m and 0<=nj<n and grid[ni][nj]>1:\n                    id=grid[ni][nj]\n                    if id not in seen:\n                        ans+=mp[id]\n                        seen.add(id)\n            return ans\n        def dfs(i,j,id):\n            nonlocal cnt\n            cnt+=1\n            grid[i][j]=id\n            for di,dj in directions:\n                ni,nj=i+di,j+dj\n                if 0<=ni<m and 0<=nj<n and grid[ni][nj]==1:\n                    dfs(ni,nj,id)\n        id=2\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j]==1:\n                    cnt=0\n                    dfs(i,j,id)\n                    mp[id]=cnt\n                    id+=1\n        for i in range(m):\n            for j in range(n):\n                if grid[i][j]==0:\n                    mmax=max(mmax,solve(i,j))\n        return mmax if mmax>0 else m*n\n\n\n\n```
['Depth-First Search', 'Python3']