1568. Minimum Number of Days to Disconnect Island

T: O( (mn)^2 )
S: O(1)

class Solution {
    private int m;
    private int n;
    private static final int[][] DIRS = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    
    public int minDays(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        
        int count = getIslandCount(grid);
        if (count != 1) {
            return 0;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    grid[i][j] = 0;
                    count = getIslandCount(grid);
                    if (count != 1) { // 0 is also the ans , use != 1
                        return 1;
                    }
                    grid[i][j] = 1;
                }
            }
        }
        return 2;
    }
    private int getIslandCount(int[][] grid) {
        
        int count = 0;
        boolean[][] visited = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    bfs(grid, i, j, visited);
                    count++;
                    if (count != 1) {
                        return 2;
                    }
                }
            }
        }
        return count;
    }
    
    private void bfs(int[][] grid, int i, int j, boolean[][] visited) {
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{i, j});
        visited[i][j] = true;
        
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int curX = cur[0];
            int curY = cur[1];
            for (int[] dir : DIRS) {
                int x = curX + dir[0];
                int y = curY + dir[1];
                if (!isValid(x, y) || visited[x][y] || grid[x][y] != 1) {
                    continue;
                }
                queue.offer(new int[]{x, y});
                visited[x][y] = true;
            }
        }
    }
    private boolean isValid(int x, int y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }
}

/*
1 represents land and 0 represents water

這題一開始都只有一個島, 目標是 change 幾次, 可以變成  > 1 島（最少2個
tricky 的是 其實最大只要 2 次就可以達標
所以答案只有 0, 1, 2 這三種
所以排除了 0, 1 剩下就只有 2(因為2很難算出..so 用排除法)

disconnected => goal is to get > 1 islands

1. 0 days
if original get > 1 islands => return 0 days

2. 1 days
dfs change one cell to 0, get > 1 islands => return 1 days

3. 2 days
others 2 days (because for corner, at most 2 days, can change into two island)


   xxx
  xxxx 
    x
    
   xxo 選在 corner, 這個 1 只有 2面是 1, 把這點變成 o, 再配上另一個 o. 必定可以使島 disconnected 
  xxox 所以最多是 2 次
    x

   T: O( (mn)^2 )
   S: O(1)
    
    
*/

use tarjan's algorithm

O(mn)

https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/discuss/822726/Java-Clean-Tarjan-O(mn)