Detailed Explanation of DSU Approach + Diagrams + Annotated Code [Python3]
0. Understanding the Problem\nGiven: A binary matrix\nGoal: Return the largest possible island if we can flip one 0 to 1. Think about it this way: flipping the 
## 0. Understanding the Problem\nGiven: A binary matrix\nGoal: Return the largest possible island if we can flip one `0` to `1`. Think about it this way: flipping the *special* index from 0 to 1 is able to connect neighbouring islands, thus forming the largest island possible.\n\nExample:\n![](https://i.imgur.com/tb1Zj9m.png)\n\nIn this case, forming a bridge of sorts between the top two islands is the best option, like so:\n\n![](https://i.imgur.com/aAyuBGe.png)\n\n## 1. Analogy\nThink of the 0s as sea/ocean and 1s as land. On this land are living people. Each land piece of 1x1 has thus one person. \n\nGoal is to find the location of bridge. We only have one, and it too spans 1x1 block.\n\nNow while these islanders are happy on their own, to govern the territory, they appoint kings. These kings are the *representative* of the entire island. \n\nEach islander can thus start as their own kings, but as they take note of their *neighbouring* territories, they have to battle it out. The king with the bigger territory wins, and takes command over the other\'s lands. In case there is a tie, we make the first one (index wise) to be the king.\n\nThe kings for our map are thus marked with a flag.\n![](https://i.imgur.com/XeeIG58.png)\n\n## 2. Translation & DSU\nThis problem can thus be solved by DSU. \n\n- Each "king" is just the representative of a particular disjoint set.\n- The battle is just "union" of the sets. The bigger king wins because its the most efficient in allocation.\n- Each "islander" starts as their own "king", aka in the DSU, `king[u] = u`.\n- For taking account of their "land sizes", we have another dictionary, `size[u] = 1`, initialised by 1.\n\n\nNow the solution will make sense. **For each cell in the map/grid, find if the sum of territories held by kings is the maximum possible or not.**\n\n## 3. Annotated Code\n```\nclass DSU:\n    def __init__(self):\n        self.king = {} # king = {location:location_of_king}\n        self.size = {} # size[location] = size of territory under the king\n    \n    # initially, every islander is king\n    # and territory size is 1\n    def make_king(self, u):\n        self.king[u] = u\n        self.size[u] = 1\n\t\n\t# returns the king of a particular islander\n    def find_king(self, u):\n        if self.king[u] == u:\n            return u\n        self.king[u] = self.find_king(self.king[u]) # path compression, check references\n        return self.king[u]\n    \n\t# kings battle it out. first we find the rulers of lands u and v\n    def unite_kings(self, u, v):\n        u = self.find_king(u)\n        v = self.find_king(v)\n        \n        if u == v: return\n        if not self.size[u] > self.size[v]: u, v = v, u    \n        # u gets the territory\n        self.size[u] += self.size[v]\n        self.king[v] = self.king[u] # v is now ruled by u\n\n    \nclass Solution:\n\t# returns valid neighbours of graph with a particular value\n\t# if val is None, return both 0s and 1s containing neighbours\n    def get_neighbours(self, u, val=None):\n        r, c = u\n        ans = []\n        for dr, dc in zip([-1, 1, 0, 0], [0, 0, 1, -1]):\n            nr, nc = r+dr, c+dc\n            if 0 <= nr < self.n and 0 <= nc < self.n: # if in the valid range\n                if val == 0 and self.grid[nr][nc] == 0: ans.append((nr, nc))\n                if val == 1 and self.grid[nr][nc] == 1: ans.append((nr, nc))\n                if val is None: ans.append((nr, nc))\n        return ans\n\n    def largestIsland(self, grid: List[List[int]]) -> int:\n        dsu = DSU()\n        self.grid = grid\n        self.n = len(grid)\n        \n        for r in range(self.n):\n            for c in range(self.n):\n                if grid[r][c]:\n                    dsu.make_king((r, c)) # each islander is made king initially\n        \n        for r in range(self.n):\n            for c in range(self.n):\n                if grid[r][c]:\n                    for neighbour in self.get_neighbours((r, c), val=1):\n                        dsu.unite_kings(neighbour, (r, c)) # the kings battle it out\n\n        ans = -inf\n        for r in range(self.n):\n            for c in range(self.n):\n                if not grid[r][c]:\n\t\t\t\t# finding the unique kings surrounding the current location\n                    kings = list(set([dsu.find_king(neighbour) for neighbour in self.get_neighbours((r, c), val=1)]))\n\t\t\t\t\t# getting the sum of all of their sizes\n\t\t\t\t\t# +1 because the current cell is also becoming 1 from a 0\n                    ans = max(ans, 1+sum([dsu.size[king] for king in kings]))\n\n\t\t# if no cell is accessed, all are 1s.\n        if ans == -inf: ans = self.n*self.n\n        return ans\n```\n\n## 4. References\nhttps://cp-algorithms.com/data_structures/disjoint_set_union.html\n\nAny questions? Ask! Comments and criticisms are welcome. An upvote lets me know this is helpful!
['Python', 'Python3']