<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
    const vector<vector<int>> DIRECTIONS = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int m, n;

    struct ArticulationPointInfo {
        bool hasArticulationPoint;
        int time;

        ArticulationPointInfo(bool hasArticulationPoint, int time) : hasArticulationPoint(hasArticulationPoint), time(time) {}
    };

    // Check if the given cell is a valid land cell
    bool isValidLandCell(const vector<vector<int>>& grid, int i, int j) 
    {
        return i>=0 && i<m && j>=0 && j<n && grid[i][j] == 1;
    }

    void findArticulationPoints(vector<vector<int>>& grid, int i, int j,
                                vector<vector<int>>& discoveryTime,
                                vector<vector<int>>& lowestReachable,
                                vector<vector<int>>& parentCell,
                                ArticulationPointInfo& apInfo) 
    {
        discoveryTime[i][j] = lowestReachable[i][j] = apInfo.time++;

        int children = 0;

        // Explore all adjacent cells
        for (const auto& direction : DIRECTIONS) {
            int x = i + direction[0];
            int y = j + direction[1];
    
            if (isValidLandCell(grid, x, y)) 
            {
                int nei = x*n + y;

                if (discoveryTime[x][y] == -1) 
                {
                    children++;
                    parentCell[x][y] = i * n + j;  // Set parent
                    findArticulationPoints(grid, x, y, discoveryTime, lowestReachable, parentCell, apInfo);

                    // Update lowest reachable time
                    lowestReachable[i][j] = min(lowestReachable[i][j], lowestReachable[x][y]);

                    // Check for articulation point condition
                    if (lowestReachable[x][y] >= discoveryTime[i][j] && parentCell[i][j] != -1)
                        apInfo.hasArticulationPoint = true;
                } 
                else if (nei != parentCell[i][j]) 
                    lowestReachable[i][j] = min(lowestReachable[i][j], discoveryTime[x][y]);    // Update lowest reachable time for back edge
            }
        }

        // Root of DFS tree is an articulation point if it has more than one child
        if (parentCell[i][j] == -1 && children > 1)
            apInfo.hasArticulationPoint = true;
    }

public:
    int minDays(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        ArticulationPointInfo apInfo(false, 0);
        int landCells = 0, islandCount = 0;

        // Arrays to store information for each cell
        vector<vector<int>> discoveryTime(m, vector<int>(n, -1));       // Time when a cell is first discovered
        vector<vector<int>> lowestReachable(m, vector<int>(n, -1));     // Lowest discovery time reachable from the subtree rooted at this cell
        vector<vector<int>> parentCell(m, vector<int>(n, -1));          // Parent of each cell in DFS tree

        // Traverse the grid to find islands and articulation points
        for (int i = 0; i < m; i++) 
        {
            for (int j = 0; j < n; j++) 
            {
                if (grid[i][j] == 1) 
                {
                    landCells++;
                
                    // not visited
                    if (discoveryTime[i][j] == -1) 
                    {  
                        // Start DFS for a new island
                        findArticulationPoints(grid, i, j, discoveryTime,
                                               lowestReachable, parentCell,
                                               apInfo);
                        islandCount++;
                    }
                }
            }
        }

        // Determine the minimum number of days to disconnect the grid
        if (islandCount == 0 || islandCount >= 2)
            return 0;                  // Already disconnected or no land
        if (landCells == 1) return 1;  // Only one land cell
        if (apInfo.hasArticulationPoint)
            return 1;  // An articulation point exists
        return 2;      // Need to remove any two land cells
    }
};
12700