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

import random
from collections import defaultdict


class Solution:
    def minDays(self, grid: List[List[int]]) -> int:
        # for row in grid:
        #     x = ["#" if v else " " for v in row]
        #     print("".join(x))

        n = len(grid)
        m = len(grid[0])

        def bfs(r, c, new_val):  # returns size
            res = 1
            q = [r, c]
            grid[r][c] = new_val
            while q:
                x = q.pop(0)
                y = q.pop(0)
                dr, dc = 1, 0
                for i in range(4):
                    nr, nc = x + dr, y + dc
                    dr, dc = dc, -dr
                    if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 1:
                        grid[nr][nc] = new_val
                        res += 1
                        q.append(nr)
                        q.append(nc)
            return res

        island_size = 0
        num_islands = 0

        for r, row in enumerate(grid):
            for c, val in enumerate(row):
                if val == 1:
                    num_islands += 1
                    if num_islands > 1:
                        return 0
                    island_size = bfs(r, c, 2)
        if num_islands == 0:
            return 0
        if island_size == 1:
            return 1
        if island_size == 2:
            return 2
        if island_size == 3:
            return 1

        is_mp = {}  # (r, c) -> id
        for r, row in enumerate(grid):
            for c, val in enumerate(row):
                if val == 2:
                    is_mp[(r, c)] = len(is_mp)

        zzz = len(is_mp)
        edges = []
        for r, row in enumerate(grid):
            for c, val in enumerate(row):
                if val == 2:
                    is_id = is_mp[(r, c)]
                    dr, dc = 0, -1
                    for i in range(2):
                        nr, nc = r + dr, c + dc
                        dr, dc = dc, -dr
                        if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] == 2:
                            is_id_2 = is_mp[(nr, nc)]
                            edges.append((is_id, is_id_2))

        def get_root(par, a):
            if par[a] < 0:
                return a
            par[a] = get_root(par, par[a])
            return par[a]

        def unite(par, a, b):
            pa = get_root(par, a)
            pb = get_root(par, b)
            if pa == pb:
                return 1 / 0
            pa_size = -par[pa]
            pb_size = -par[pb]
            if pa_size > pb_size:
                # root a bigger tree
                par[pb] = pa
                par[pa] -= pb_size
            else:
                par[pa] = pb
                par[pb] -= pa_size

        def karger():
            roots = [-1] * zzz
            nodes = zzz
            random.shuffle(edges)
            i = 0
            while nodes > 2:
                e = edges[i]
                i += 1
                while get_root(roots, e[0]) == get_root(roots, e[1]):
                    e = edges[i]
                    i += 1
                unite(roots, e[0], e[1])
                nodes -= 1
            res = 0
            g = defaultdict(set)
            for e in edges[i:]:
                fr = get_root(roots, e[0])
                to = get_root(roots, e[1])
                if fr != to:
                    # res += 1
                    g[e[0]].add(e[1])
                    g[e[1]].add(e[0])
            sorted_nodes = [(x, len(g[x])) for x in g.keys()]
            sorted_nodes.sort(key=lambda x: -x[1])
            # print(g)
            # print(roots)
            for node, _ in sorted_nodes:
                if roots[node] == -1:
                    # it's a root, single node, I can't remove it
                    continue
                # remove this node
                # print('Remove %d' % node)
                for ng in g[node]:
                    g[ng].remove(node)
                    if len(g[ng]) == 0:
                        g.pop(ng, None)
                g.pop(node, None)
                res += 1
                if len(g) == 0:
                    # print('Found all!!!')
                    break
            return res

        res = 1e9
        for i in range(50):
            res = min(res, karger())
            if res == 1:
                # print("Iterations: %d" % i)
                return 1
        return res

179