Method minDays

MinimumNumberofDaystoDisconnectIsland.java:17–56

(int[][] grid)

    static boolean hasArticulationPoint; //tells if graph has an articulation point
    static int time; //global time counter used by DFS
    public int minDays(int[][] grid) {
        rows = grid.length; 
        cols = grid[0].length;
        hasArticulationPoint = false;
        time = 0;
        int landCells = 0, islandCount = 0;

        int[][] discoveryTime = new int[rows][cols]; // Time when a cell is first discovered
        // Lowest discovery time reachable from the subtree rooted at this cell
        int[][] lowestReachable = new int[rows][cols]; 
        // Parent of each cell in DFS tree
        int[][] parentCell = new int[rows][cols]; 

        // Initialize arrays with default values (note -1 means there is no parent)
        for (int i = 0; i < rows; i++) {
            Arrays.fill(discoveryTime[i], -1);
            Arrays.fill(lowestReachable[i], -1);
            Arrays.fill(parentCell[i], -1);
        }

        // Traverse the grid to find islands and articulation points
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) { //1 means a node in graph.
                    landCells++;
                    if (discoveryTime[i][j] == -1) { // If not yet visited
                        // Start DFS for a new island
                        findArticulationPoints(grid,i,j,discoveryTime,lowestReachable,parentCell);
                        islandCount++; //no of dfs calls means number of connected components
                    }
                }
            }
        }

        // Determine the minimum number of days to disconnect the grid
        if (islandCount == 0 || islandCount >= 2) return 0; // Already disconnected or no land
        if (landCells == 1) return 1; // Only one land cell
        if (hasArticulationPoint) return 1; // An articulation point exists
        return 2; // Need to remove any two land cells
    }

    private void findArticulationPoints(int[][] grid,int row,int col,int[][] discoveryTime,int[][] lowestReachable,int[][] parentCell) {
        discoveryTime[row][col] = time; //first node discovery is 0, note that time is global