Problem statement

https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/

Solution

Actually the answer for this question can be only 0, 1 or 2. We can remove each point and check if we have more than one component or not.

Complexity

Time complexity will be O(m^2n^2).

Code

class Solution:
    def minDays(self, grid):
        m, n, self.v = len(grid), len(grid[0]), set()
        total = sum(sum(row) for row in grid)

        def dfs(x, y):
            self.v.add((x, y))
            for dx, dy in (x+1, y), (x, y+1), (x, y-1), (x-1, y):
                if not 0 <= dx < n or not 0 <= dy < m: continue
                if grid[dy][dx] == 0 or (dx, dy) in self.v: continue
                dfs(dx, dy)
                
        def check(tot):
            self.v = set()
            for x, y in product(range(n), range(m)):
                if grid[y][x] == 1: 
                    dfs(x, y)
                    break
            return len(self.v) != tot or tot == 0
        
        if check(total): return 0
        for x, y in product(range(n), range(m)):
            if grid[y][x] == 1:
                grid[y][x] = 0
                if check(total - 1): return 1
                grid[y][x] = 1
        
        return 2

Remark

There is also solution, using articulation points with O(mn) complexity: if graph is not connected, return 0, if it has at least one articulation point: return 1 and else return 2