<p>You are given two <code>m x n</code> binary matrices <code>grid1</code> and <code>grid2</code> containing only <code>0</code>&#39;s (representing water) and <code>1</code>&#39;s (representing land). An <strong>island</strong> is a group of <code>1</code>&#39;s connected <strong>4-directionally</strong> (horizontal or vertical). Any cells outside of the grid are considered water cells.</p>

<p>An island in <code>grid2</code> is considered a <strong>sub-island </strong>if there is an island in <code>grid1</code> that contains <strong>all</strong> the cells that make up <strong>this</strong> island in <code>grid2</code>.</p>

<p>Return the <em><strong>number</strong> of islands in </em><code>grid2</code> <em>that are considered <strong>sub-islands</strong></em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/10/test1.png" style="width: 493px; height: 205px;" />
<pre>
<strong>Input:</strong> grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
<strong>Output:</strong> 3
<strong>Explanation: </strong>In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are three sub-islands.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/06/03/testcasex2.png" style="width: 491px; height: 201px;" />
<pre>
<strong>Input:</strong> grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
<strong>Output:</strong> 2 
<strong>Explanation: </strong>In the picture above, the grid on the left is grid1 and the grid on the right is grid2.
The 1s colored red in grid2 are those considered to be part of a sub-island. There are two sub-islands.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid1.length == grid2.length</code></li>
	<li><code>n == grid1[i].length == grid2[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 500</code></li>
	<li><code>grid1[i][j]</code> and <code>grid2[i][j]</code> are either <code>0</code> or <code>1</code>.</li>
</ul>

class DisJointSets():
    def __init__(self,N):
        # Initially, all elements are single element subsets
        self._parents = [node for node in range(N)]
        self._ranks = [1 for _ in range(N)]

    def find(self, u):
        while u != self._parents[u]:
            # path compression technique
            self._parents[u] = self._parents[self._parents[u]]
            u = self._parents[u]
        return u

    def connected(self, u, v):
        return self.find(u) == self.find(v)

    def union(self, u, v):
        # Union by rank optimization
        root_u, root_v = self.find(u), self.find(v)
        if root_u == root_v:
            return True

        # I modified this to have proper rank sizes
        if self._ranks[root_u] > self._ranks[root_v]:
            self._parents[root_v] = root_u
            self._ranks[root_u] += self._ranks[root_v]
        elif self._ranks[root_v] > self._ranks[root_u]:
            self._parents[root_u] = root_v
            self._ranks[root_v] += self._ranks[root_u]
        else:
            self._parents[root_u] = root_v
            self._ranks[root_v] += self._ranks[root_u]
        return False
    join = union

    def n_components(self):
        return sum(parent == i for i, parent in enumerate(self._parents))

    def copy(self):
        new = DisJointSets(len(self._parents))
        new._parents = self._parents[:]
        new._ranks = self._ranks[:]
        return new

    def components(self):
        componentsByRoot = defaultdict(list)
        for i in range(len(self._parents)):
            componentsByRoot[self.find(i)].append(i)
        return componentsByRoot.values()



class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        h = height = len(grid1)
        w = width = len(grid1[0])

        # Get the first set of islands.
        dsu1 = DisJointSets(h*w)
        for r in range(h):
            for c in range(w):
                if c+1<w and grid1[r][c] == 1 and grid1[r][c+1] == 1:
                    dsu1.join(r*w + c, r*w+c+1)
                if r+1<h and grid1[r][c] == 1 and grid1[r+1][c] == 1:
                    dsu1.join(r*w+c, (r+1)*w+c)
        
        # get the second set of islands.
        dsu2 = DisJointSets(h*w)
        for r in range(h):
            for c in range(w):
                if c+1<w and grid2[r][c] == 1 and grid2[r][c+1] == 1:
                    dsu2.join(r*w + c, r*w+c+1)
                if r+1<h and grid2[r][c] == 1 and grid2[r+1][c] == 1:
                    dsu2.join(r*w+c, (r+1)*w+c)
        
        # Check all that the second set of islands touches.
        islandTouching = defaultdict(set)

        for r in range(h):
            for c in range(w):
                if grid2[r][c] == 1:
                    islandTouching[dsu2.find(r*w+c)].add(dsu1.find(r*w+c) if grid1[r][c] == 1 else -1)
        
        num_islands = 0
        for islandAdjacent in islandTouching.values():
            if len(islandAdjacent) == 1 and -1 not in islandAdjacent:
                num_islands += 1
        return num_islands


2669