Disconnect the ‘GRID’ by removing the minimum number of cities

Observation: The answer is always less than equal to two (‘<= 2’).

Proof: For any state (with ‘>= 3’ cities), every city at its boundary is connected to ‘<= 3’ cities, and between those cities, there will be at least one city connected to exactly two other cities. This city (colored red) can be of one of the following four types:

If we remove the two grey-colored cities, then the city with red color will get disconnected from its state. Now, we know that the answer will never be greater than ‘2’. 

To check if the ‘GRID’ is disconnected, we can do a Depth-first search (or Breadth-first search) traversal for any arbitrary city and mark all the reachable cities from it. If some cities remain unmarked, then the ‘GRID’ is disconnected.
 

We try to find if the ‘GRID’ can be disconnected by removing:

• Zero cities: If the grid doesn’t contain any city or contains more than one state (already disconnected), the answer is ‘0’.
• One city: Iterate through the ‘GRID’, remove one city, and check if the ‘GRID’ becomes disconnected. If it stays connected, put the city back into the ‘GRID’ and check for the next city, and so on. If the ‘GRID’ becomes disconnected at any point during the iteration, return ‘1’ as the answer.
• Two cities: If the ‘GRID’ cannot be disconnected by removing one city, then we know that it can always be disconnected by removing ‘2’ cities. So, return ‘2’ as the answer.

The ‘isDisconnected()’ function to check if the ‘GRID’ is disconnected:

• Set ‘count = 0’. To count the number of states (connected components) in ‘GRID’.
• Initialize a 2D array ‘seen[n][m]’ and set it to ‘False’. Use it to mark visited cities.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
  • Run a loop where ‘j’ ranges from ‘0’ to ‘M - 1’:
    • If ‘GRID[i][j] == 1’ and ‘seen[i][j] == False’, then we have not visited the city ‘(i, j)’:
      • ‘count += 1’. Increase the number of states.
      • If ‘count’ is greater than ‘1’, then ‘GRID’ is disconnected:
        • Return ‘True’.
      • Call ‘dfs(i, j)’ to mark the cities connected to ‘(i, j)’ as visited.
• If ‘count == 0’, then there are no cities in ‘GRID’:
  • Return ‘True’.
• Return ‘False’ as the ‘GRID’ is connected (contains exactly one state).

The ‘dfs(integer x, integer y)’ function to mark all the cities connected to ‘(x, y)’:

• Initialize a 2D array ‘dir[4][2] = [ [0, 1], [1, 0], [0, -1], [-1, 0] ]’. Use it to move to the adjacent cell in ‘GRID’.
• Set ‘seen[x][y] = True’.
• Run a loop where ‘i’ ranges from ‘0’ to ‘3’, to move to the adjacent cities:
  • Set ‘newX = x + dir[i][0]’ and ‘newY = y + dir[i][1]’. This is the location of the cell adjacent to ‘(x, y)’.
  • If ‘newX >= 0’ and ‘newX < n’ and ‘newY >= 0’ and ‘newY < n’, then ‘(newX, newY)’ is a valid cell:
    • If ‘GRID[newX][newY] == 1’ and ‘seen[newX][newY] == False’, then move to the new city:
      • ‘dfs(newX, newY)’.

Algorithm:

• If ‘isDisconnected() == True’, then the ‘GRID’ is already disconnected:
  • Return ‘0’ as the answer.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
  • Run a loop where ‘j’ ranges from ‘0’ to ‘M - 1’:
    • If ‘GRID[i][j] == 1’, then:
      • Set ‘GRID[i][j] = 0’. Remove the city from ‘GRID’.
      • If ‘isDisconnected() == True’, then the ‘GRID’ has become disconnected:
        • Return ‘1’ as the answer.
      • Set ‘GRID[i][j] = 1’. Insert the city back into the ‘GRID’.
• Return ‘2’ as the answer. As the ‘GRID’ cannot be disconnected by removing one city.

O((N*M)^2), where ‘N’ is the number of rows in ‘GRID’, and ‘M’ is the number of columns in ‘GRID’.

In the worst-case scenario, there are ‘O(N*M)’ cities. For each city, we check if the ‘GRID’ becomes disconnected after removing it in ‘O(N*M)’. Thus, the time complexity is ‘O((N*M)^2)’.

O(N*M), where ‘N’ is the number of rows in ‘GRID’, and ‘M’ is the number of columns in ‘GRID’.

The DFS stack size will be equal to the number of cities, i.e., ‘O(N*M)’. The ‘seen’ array also needs ‘O(N*M)’ space.