You are given two m x n binary matrices grid1 and grid2 containing only 0's (representing water) and 1's (representing land). An island is a group of 1's connected 4-directionally (horizontal or vertical). Any cells outside of the grid are considered water cells.

An island in grid2 is considered a sub-island if there is an island in grid1 that contains all the cells that make up this island in grid2.

Return the number of islands in grid2 that are considered sub-islands.

Example 1:

Input: 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]]
Output: 3
Explanation: 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.

Example 2:

Input: 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]]
Output: 2 
Explanation: 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.

Constraints:

• m == grid1.length == grid2.length
• n == grid1[i].length == grid2[i].length
• 1 <= m, n <= 500
• grid1[i][j] and grid2[i][j] are either 0 or 1.

瞅一眼标题就知道可以用并查集（Union Find）来解答。扫一眼题目感觉这道题挺复杂，输入有两个矩阵，要判断第二个矩阵的岛屿是否是第一个矩阵的岛屿的子岛屿。感觉需要对两个矩阵做岛屿合并然后再进行比较。其实再细读一遍题目就会发现并没有那么复杂。

第二个矩阵的岛屿是否是第一个矩阵的岛屿的子岛屿，那第二个矩阵的岛屿的每一块陆地都应该属于第一矩阵的一个岛。第二个矩阵的岛屿不是第一个矩阵岛屿的子岛屿需要满足以下两种情况：

1）第二个矩阵的岛屿中只要一块陆地在第一个矩阵中是水。

2）第二个矩阵的岛屿中的陆地分布在第一个矩阵的多个岛屿上。

其实上述情况2可以不用考虑，因为同一个岛屿的陆地是相连的，如果该岛屿有多个陆地分布在第一个矩阵的多个岛屿上，那肯定一块或多块陆地在第一个矩阵中是水。

根据以上分析，题目就可以简化为在合并第二块矩阵的每块陆地时，再判断下其在第一个矩阵中是否是水，如果是水就把合并的岛屿标注为非子岛屿。

算法实现：

1）对第二个矩阵用Union Find进行岛屿合并，几乎可以照搬之前的模板代码LeetCode305. Number of Islands II 。唯一改动是增加一个数组用于标注合并后的岛屿是否为子岛屿。

2）遍历第二个矩阵，每遇到一块陆地，进行岛屿合并，同时判断它在第一个矩阵中是否为水，如果是水则与其合并的岛屿为非子岛屿，以后与该陆地合并的岛屿将都为非子岛屿。

3）再遍历一遍第二个矩阵，统计中所有子岛屿的个数。

class UnionFind :
    def __init__(self, n) :
        self.parent = [-1] * n
        self.size = [0] * n
        self.isSub = [True] * n
        
    def find(self, x) :
        if self.parent[x] != x :
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def merge(self, x, y) :
        px, py = self.find(x), self.find(y)
        #两个同属一个岛屿直接返回，否则进行合并
        if px == py :
            return
        
        #小岛合并到大岛，为了提高查找的效率
        if self.size[px] > self.size[py] :
            self.parent[py] = px
            self.size[px] += self.size[py]
            self.isSub[px] &= self.isSub[py]
        else :
            self.parent[px] = py
            self.size[py] += self.size[px]
            self.isSub[py] &= self.isSub[px]
        
    #增加一新陆地需要进行更新parent
    def updateParent(self, x, sub) :
        if self.parent[x] == -1 :
            self.parent[x] = x
            self.size[x] = 1
            self.isSub[x] = sub
class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m, n = len(grid2), len(grid2[0])
        
        uf = UnionFind(m * n)
        
        for i in range(m) :
            for j in range(n) :
                if grid2[i][j] == 1 :
                    uf.updateParent(i * n + j, grid1[i][j] == 1)
                    if i - 1 >= 0 and grid2[i - 1][j] == 1 :
                        uf.merge(i * n + j, (i - 1) * n + j )
                    if j - 1 >= 0 and grid2[i][j - 1] == 1 :
                        uf.merge(i * n + j, i * n + j - 1)  
        res = 0
        for i in range(m) :
            for j in range(n) :
                index = i * n + j
                if grid2[i][j] == 1 and uf.find(index) == index and uf.isSub[index]:
                    res += 1
        
        return res