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


struct vDCC {
    int n, tot = 0, root, cnt = 0, num; // n从1开始
    vector<vector<int>> e, ne; // new e新图，就是缩点之后的图
    vector<int> dfn, low;

    vDCC() {}
    vDCC(int n)
        : n(n), tot(0), cnt(0), e(n + 5), ne(n + 5), dfn(n + 5, 0), low(n + 5) {
    }
    void addEdge(int a, int b) {
        e[a].push_back(b);
        e[b].push_back(a);
    }
    bool build() {
        for (root = 1; root <= n; ++root) {
            if (e.size() && !dfn[root])
                if (Tarjan(root))
                    return true;
        }
        return false;
    }

    void tarjan(int x) {
        root = x;
        Tarjan(x);
    }

    bool Tarjan(int x) {
        dfn[x] = low[x] = ++tot;
        int child = 0;
        for (int y : e[x]) {
            if (!dfn[y]) { // 若y尚未访问
                if (Tarjan(y))
                    return true;
                low[x] = min(low[x], low[y]);
                if (low[y] >= dfn[x]) {
                    child++;
                    if (x != root || child > 1) {
                        return true;
                    }
                    cnt++;
                }
            } else { // 若y已经访间
                low[x] = min(low[x], dfn[y]);
            }
        }
        return false;
    }
};

struct DSU {
    std::vector<int> fa, siz;

    DSU() {}

    DSU(int n) { init(n); }

    void init(int n) {
        fa.resize(n);
        std::iota(fa.begin(), fa.end(), 0);
        siz.assign(n, 1);
    }

    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

    bool same(int x, int y) { return find(x) == find(y); }

    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        fa[y] = x;
        return true;
    }

    int size(int x) { return siz[find(x)]; }
};

pair<int, int> d[2] = {{1, 0}, {0, 1}};

class Solution {
public:
    int n, m;
    int getid(int x, int y) { return x * m + y + 1; }
    int minDays(vector<vector<int>>& g) {
        n = g.size(), m = g[0].size();
        int cnt = 0;
        vDCC dcc(n * m);
        DSU dsu(n * m + 5);
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (g[i][j]) {
                    ++cnt;
                    for (auto it : d) {
                        auto x = it.first, y = it.second;
                        if (i + x >= n || j + y >= m || g[i + x][j + y] != 1)
                            continue;
                        dsu.merge(getid(i, j), getid(i + x, j + y));
                        dcc.addEdge(getid(i, j), getid(i + x, j + y));
                        g[i][j] = 0;
                    }
                }
            }
        }

        if (cnt <= 1) //直接删除
            return cnt;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (g[i][j]) {
                    if (dsu.size(getid(i, j)) != cnt)//不止一个陆地
                        return 0;
                    else
                        break;
                }
            }
        }

        if (dcc.build())
            return 1;
        else
            return 2;
    }
};

16060