<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>

#pragma GCC optimize("O3")

// Union Find data structure
// Taken and modified from
// https://github.com/kartikkukreja/blog-codes/blob/master/src/Union%20Find%20%28Disjoint%20Set%29%20Data%20Structure.cpp
class UF {
    int cnt;
    std::vector<int> id, sz;

  public:
    // Create an empty union find data structure with N isolated sets.
    UF(int N) {
        cnt = N;
        id.resize(N);
        sz.resize(N);
        for (int i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }

    // Return the id of component corresponding to object p.
    // also implemented with path compression
    int find(int p) {
        if (p == id[p])
            return p;
        return id[p] = find(id[p]);
    }

    // Replace sets containing x and y with their union.
    void merge(int x, int y) {
        int i = find(x);
        int j = find(y);
        if (i == j)
            return;

        // make smaller root point to larger one
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
        cnt--;
    }

    // Return the number of disjoint sets.
    int count() {
        return cnt;
    }
};

class Solution {
  private:
    int m, n;
    bool hasArticulationPoint = false;

    int countIsland(std::vector<std::vector<int>> &grid) {
        UF uf(m * n);
        int waterCount = 0;
        bool hasOneAdjancentLand = false;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c]) {
                    int currentPosition = r * n + c;
                    int surroundingGridSum = 0;
                    if (r - 1 >= 0 && grid[r - 1][c]) {
                        uf.merge(currentPosition, (r - 1) * n + c);
                        surroundingGridSum++;
                    }
                    if (r + 1 < m && grid[r + 1][c]) {
                        uf.merge(currentPosition, (r + 1) * n + c);
                        surroundingGridSum++;
                    }
                    if (c - 1 >= 0 && grid[r][c - 1]) {
                        uf.merge(currentPosition, r * n + c - 1);
                        surroundingGridSum++;
                    }
                    if (c + 1 < n && grid[r][c + 1]) {
                        uf.merge(currentPosition, r * n + c + 1);
                        surroundingGridSum++;
                    }
                    if (surroundingGridSum == 1)
                        hasOneAdjancentLand = true;
                } else
                    waterCount++;
            }
        }
        int landCellCount = m * n - waterCount;
        hasArticulationPoint = (landCellCount == 1) || (hasOneAdjancentLand && (landCellCount) > 2);
        return uf.count() - waterCount;
    }

  public:
    int minDays(std::vector<std::vector<int>> &grid) {
        m = grid.size();
        n = grid.front().size();
        if (countIsland(grid) != 1)
            return 0;
        else if (hasArticulationPoint)
            return 1;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c]) {
                    // try to change a land cell into a water cell
                    grid[r][c] = 0;
                    if (countIsland(grid) != 1)
                        return 1;
                    grid[r][c] = 1;
                }
            }
        }
        return 2;
    }
};
22780