Minimum Number of Days to Disconnect Island LeetCode solution in Python

1
class Solution:
2
    def minDays(self, grid: List[List[int]]) -> int:
3
        rows, cols = len(grid), len(grid[0])
4

5
        disc_time = [[-1 for _ in range(cols)] for _ in range(rows)]
6
        low_value = [[-1 for _ in range(cols)] for _ in range(rows)]
7
        parents = [[(-1, -1) for _ in range(cols)] for _ in range(rows)]
8
        is_ap = [[False for _ in range(cols)] for _ in range(rows)]
9
        dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]
10

11
        time = 0
12
        has_ap = False
13

14
        def dfs(i, j):
15
            if grid[i][j] == 0:
16
                return
17
            nonlocal time
18
            nonlocal has_ap
19
            disc_time[i][j] = time
20
            low_value[i][j] = time
21
            time += 1
22

23
            child = 0
24
            for di, dj in dirs:
25
                ni, nj = i + di, j + dj
26
                if not (0 <= ni < rows) or not (0 <= nj < cols):
27
                    continue
28
                if grid[ni][nj] != 1:
29
                    continue
30

31
                if disc_time[ni][nj] == -1:  # not visited
32
                    child += 1
33
                    parents[ni][nj] = (i, j)
34
                    dfs(ni, nj)
35
                    low_value[i][j] = min(low_value[i][j], low_value[ni][nj])
36

37
                    if parents[i][j] == (-1, -1) and child > 1:
38
                        is_ap[i][j] = True
39
                        has_ap = True
40

41
                    if (
42
                        parents[i][j] != (-1, -1)
43
                        and low_value[ni][nj] >= disc_time[i][j]
44
                    ):
45
                        is_ap[i][j] = True
46
                        has_ap = True
47
                elif (ni, nj) != parents[i][j]:
48
                    low_value[i][j] = min(low_value[i][j], disc_time[ni][nj])
49

50
        sccs = 0
51
        num_ones = 0
52
        for i in range(rows):
53
            for j in range(cols):
54
                if grid[i][j] == 1:
55
                    num_ones += 1
56
                if disc_time[i][j] == -1 and grid[i][j] == 1:
57
                    dfs(i, j)
58
                    sccs += 1
59

60
        if sccs > 1:
61
            return 0
62
        elif has_ap:
63
            return 1
64
        else:
65
            if num_ones == 1:
66
                return 1
67
            elif num_ones == 0:
68
                return 0
69
        return 2