Python Union Find Solution, all nodes' parent are the upper-left corner
The nodes that we\'re going to union is not actually two grids, but the corners of two grids.\n\nSupposed we have the following grids (Same as Example 5): \n\n"
The nodes that we\'re going to union is not actually two grids, but the corners of two grids.\n\nSupposed we have the following grids (Same as Example 5): \n\n"/"   "/"\n"/"   " " \n\nWe know that each grid has 4 corners, **the nodes we are going to union is not the 4 grids, but the 9 corners of these grids.**\n\nThe intuition is that if we have a slash, the number of area can increment by 1 if it turns out that both of **its start point end end point are connected to the edge of the square**. But how do we represent start point, the end point, and the edge? We can give coordinate to those points, for example, upper-left corner is (0,0), upper-right corner is (N+1, 0), bottom-left corner (0, N+1) bottom-right corner (N+1, N+1).\n\nAs such, all edges can be represented as (0, m), (m, 0), (N+1, m), and (m, N+1). And we observed that all corners on the edges on connected... therefore, we could, at the first place, just union all the edge corner to (0,0). At this point, since each small grid have four corners, we can use these corners as positions to do union find.\n\nThe algorithm can be explained as follows: given a grid, we can transform the grid-index to its two corner indexes, depending on it is a \'/\' or \'\\\\\'. For example, given grid, `(row, col)`, the two corners are `(row+1, col)` and `(row, col+1)` if it is a `\'/\'`, otherwise they are `(row, col)` and `(row+1, col+1)`.\nWe\'d like to union these two corners. If it turns out these two corners have the same parent, it must be in the case that there is a line that both starts from and ends at the edges. Then we increment the count by 1. The count starts at 1, because at least the number of area is 1. After traverse all grids, we return the final count.\n\n\n```\nclass UnionFind:\n    def __init__(self, n):\n\t    # There are (n+1) * (n+1) corners given an n * n matrix\n        self.parent = [i for i in range((n+1) * (n+1))]\n\t\tself.rank = [0] * ((n+1) * (n+1))\n\t\t\n\t\t# connect all edge corners to upper-left corner of the square\n        for i in range(n+1):\n            self.parent[i] = 0\n            self.parent[i * (n + 1)] = 0\n            self.parent[i * (n + 1) + n] = 0\n            self.parent[n * (n + 1) + i] = 0\n        \n\t\t# always take upper-left corner as parent\n        self.rank[0] = 1\n\t\t\n\t\t# there is at least 1 area\n        self.count = 1\n    \n    def find(self, x):\n        if x != self.parent[x]:\n            self.parent[x] = self.find(self.parent[x])\n        return self.parent[x]\n    \n    def union(self, x, y):\n        px, py = self.find(x), self.find(y)\n        if px == py:\n            self.count += 1 # increment area\n        else:\n            if self.rank[px] > self.rank[py]:\n                self.parent[py] = px\n            elif self.rank[px] < self.rank[py]:\n                self.parent[px] = py\n            else:\n                self.parent[py] = px\n                self.rank[px] += 1\n        \nclass Solution:\n    def regionsBySlashes(self, grid):\n        """\n        :type grid: List[str]\n        :rtype: int\n        """\n        \n        n = len(grid)\n        uf = UnionFind(n)\n        \n        for i in range(n):\n            for j in range(n):\n                if grid[i][j] == \' \':\n                    continue\n\t\t\t\t\t\n\t\t\t\t# convert grid index to corner index + convert 2-d matrix to 1-d union find array\n                if grid[i][j] == \'/\':\n                    uf.union(i * (n+1) + (j+1), (i+1) * (n+1) + j)\n                else:\n                    uf.union(i * (n+1) + j, (i+1) * (n+1) + (j+1))\n        \n        return uf.count\n```
[]