<p>You are given an <code>m x n</code> binary grid <code>grid</code> where <code>1</code> represents land and <code>0</code> represents water. An <strong>island</strong> is a maximal <strong>4-directionally</strong> (horizontal or vertical) connected group of <code>1</code>&#39;s.</p>

<p>The grid is said to be <strong>connected</strong> if we have <strong>exactly one island</strong>, otherwise is said <strong>disconnected</strong>.</p>

<p>In one day, we are allowed to change <strong>any </strong>single land cell <code>(1)</code> into a water cell <code>(0)</code>.</p>

<p>Return <em>the minimum number of days to disconnect the grid</em>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/24/land1.jpg" style="width: 500px; height: 169px;" />
<pre>
<strong>Input:</strong> grid = [[0,1,1,0],[0,1,1,0],[0,0,0,0]]

<strong>Output:</strong> 2
<strong>Explanation:</strong> We need at least 2 days to get a disconnected grid.
Change land grid[1][1] and grid[0][2] to water and get 2 disconnected island.
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/12/24/land2.jpg" style="width: 404px; height: 85px;" />
<pre>
<strong>Input:</strong> grid = [[1,1]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> Grid of full water is also disconnected ([[1,1]] -&gt; [[0,0]]), 0 islands.
</pre>

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

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 30</code></li>
	<li><code>grid[i][j]</code> is either <code>0</code> or <code>1</code>.</li>
</ul>

# class Solution:
#     # Directions for adjacent cells: right, down, left, up
#     DIRECTIONS = [[0, 1], [1, 0], [0, -1], [-1, 0]]

#     def minDays(self, grid):
#         rows, cols = len(grid), len(grid[0])
#         ap_info = {"has_articulation_point": False, "time": 0}
#         land_cells = 0
#         island_count = 0

#         # Arrays to store information for each cell
#         discovery_time = [
#             [-1] * cols for _ in range(rows)
#         ]  # Time when a cell is first discovered
#         lowest_reachable = [
#             [-1] * cols for _ in range(rows)
#         ]  # Lowest discovery time reachable from the subtree rooted at this cell
#         parent_cell = [
#             [-1] * cols for _ in range(rows)
#         ]  # Parent of each cell in DFS tree

#         def _find_articulation_points(row, col):
#             discovery_time[row][col] = ap_info["time"]
#             ap_info["time"] += 1
#             lowest_reachable[row][col] = discovery_time[row][col]
#             children = 0

#             # Explore all adjacent cells
#             for direction in self.DIRECTIONS:
#                 new_row = row + direction[0]
#                 new_col = col + direction[1]
#                 if (
#                     0 <= new_row < rows
#                     and 0 <= new_col < cols
#                     and grid[new_row][new_col] == 1
#                 ):
#                     if discovery_time[new_row][new_col] == -1:
#                         children += 1
#                         parent_cell[new_row][new_col] = (
#                             row * cols + col
#                         )  # Set parent
#                         _find_articulation_points(new_row, new_col)

#                         # Update lowest reachable time
#                         lowest_reachable[row][col] = min(
#                             lowest_reachable[row][col],
#                             lowest_reachable[new_row][new_col],
#                         )

#                         # Check for articulation point condition
#                         if (
#                             lowest_reachable[new_row][new_col]
#                             >= discovery_time[row][col]
#                             and parent_cell[row][col] != -1
#                         ):
#                             ap_info["has_articulation_point"] = True
#                     elif new_row * cols + new_col != parent_cell[row][col]:
#                         # Update lowest reachable time for back edge
#                         lowest_reachable[row][col] = min(
#                             lowest_reachable[row][col],
#                             discovery_time[new_row][new_col],
#                         )

#             # Root of DFS tree is an articulation point if it has more than one child
#             if parent_cell[row][col] == -1 and children > 1:
#                 ap_info["has_articulation_point"] = True

#         # Traverse the grid to find islands and articulation points
#         for i in range(rows):
#             for j in range(cols):
#                 if grid[i][j] == 1:
#                     land_cells += 1
#                     if discovery_time[i][j] == -1:  # If not yet visited
#                         # Start DFS for a new island
#                         _find_articulation_points(i, j)
#                         island_count += 1

#         # Determine the minimum number of days to disconnect the grid
#         if island_count == 0 or island_count >= 2:
#             return 0  # Already disconnected or no land
#         if land_cells == 1:
#             return 1  # Only one land cell
#         print(discovery_time)
#         print(lowest_reachable)
#         if ap_info["has_articulation_point"]:
#             return 1  # An articulation point exists
#         return 2  # Need to remove any two land cells


        
class Solution:
    def dfs(self, i, j, grid, degrees) -> int:
        if degrees[i][j] != -1:
            return 
        d = 0
        degrees[i][j] = -2
        for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:
            if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 1:
                self.dfs(x, y, grid, degrees)
            else:
                d += 1
        degrees[i][j] = d
        self.n_land += 1

    def ap(self, i, j, grid, pre, low, parent):
        self.time += 1
        children = 0
        pre[(i, j)] = self.time
        low[(i, j)] = self.time
        for x, y in [(i-1, j), (i+1, j), (i, j-1), (i, j+1)]:
            if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y] == 1:
                if (x, y) not in pre:
                    parent[(x, y)] = (i, j)
                    children += 1
                    ap = self.ap(x, y, grid, pre, low, parent)
                    if ap:
                        return ap
                    low[(i, j)] = min(low[(x, y)], low[(i, j)])
                    if low[(x, y)] >= pre[(i, j)] and (i, j) in parent:
                        return (i, j)
                elif (i, j) not in parent or parent[(i, j)] != (x, y):
                    low[(i, j)] = min(low[(i, j)], pre[(x, y)])
                # if (i, j) == (1, 1):
                #     print(x, y)
                #     print(pre, low)
        if (i, j) not in parent and children > 1:
            return (i, j)
        return None

    def minDays(self, grid: List[List[int]]) -> int:
        n_islands = 0
        m, n = len(grid), len(grid[0])
        degrees = [[-1] * n for _ in range(m)]
        self.n_land = 0
        for i in range(m):
            for j in range(n):
                if degrees[i][j] == -1 and grid[i][j] == 1:
                    self.dfs(i, j, grid, degrees)
                    n_islands += 1
        if n_islands > 1 or n_islands == 0:
            return 0
        if self.n_land == 1:
            return 1
        pre, low, parent = {}, {}, {}
        self.time = -1
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    ap = self.ap(i, j, grid, pre, low, parent)
                    # print(pre, low, parent)
                    if ap:
                        return 1
                    return 2
        
        return 2
        

# {(0, 0): 0, (1, 0): 1, (2, 0): 2, (3, 0): 3, (3, 1): 4, (2, 1): 5, (1, 1): 6, (0, 1): 7, (1, 2): 8, (1, 3): 9, (0, 3): 10, (0, 4): 11, (1, 4): 12, (2, 4): 13, (3, 4): 14, (3, 3): 15, (2, 3): 16} {(0, 0): 0, (1, 0): 0, (2, 0): 0, (3, 0): 0, (3, 1): 0, (2, 1): 0, (1, 1): 0, (0, 1): 0, (1, 2): 6, (1, 3): 9, (0, 3): 9, (0, 4): 9, (1, 4): 9, (2, 4): 9, (3, 4): 9, (3, 3): 9, (2, 3): 9} {(1, 0): (0, 0), (2, 0): (1, 0), (3, 0): (2, 0), (3, 1): (3, 0), (2, 1): (3, 1), (1, 1): (2, 1), (0, 1): (1, 1), (1, 2): (1, 1), (1, 3): (1, 2), (0, 3): (1, 3), (0, 4): (0, 3), (1, 4): (0, 4), (2, 4): (1, 4), (3, 4): (2, 4), (3, 3): (3, 4), (2, 3): (3, 3)}
17500