题解 | #岛屿数量#并查集

from re import L
from operator import le
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 判断岛屿数量
# @param grid char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , grid: List[List[str]]) -> int:
        self.rs = 0
        n, m = len(grid), len(grid[0])
        father = {}
        def findFather(x):
            if x == father[x]:
                return x
            father[x] = findFather(father[x])
            return father[x]

        def unionTwo(x, y):
            x = findFather(x)
            father[x] = findFather(y)
        
        for i in range(0, m*n):
            father[i] = i
        for i in range(0, n):
            for j in range(0, m):
                if grid[i][j] == '1':
                    if i>0 and grid[i-1][j] == '1':
                        unionTwo((i-1)*m+j, i*m+j)
                    if j>0 and grid[i][j-1] == '1':
                        unionTwo(i*m+j-1, i*m+j)

        for i in range(0, n):
            for j in range(0, m):
                if grid[i][j] == '1' and father[i*m+j] == i*m + j:
                    self.rs+=1
        return self.rs