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.

An articulation point (or cut vertex) is defined as a vertex that, when removed along with associated edges, makes the graph disconnected (or, more precisely, increases the number of connected components in the graph).

We can find the articulation point by doing a Depth-first search traversal (DFS) of the graph. A node ‘u’ is said to be an articulation point if:

• ‘u’ is the root node of the DFS tree and has more than one child.
• If ‘u’ is not root, then if no vertex in the subtree rooted at ‘u’ (in the DFS tree) has a back edge to one of the ancestors of ‘u’ (in DFS tree), ‘u’ is an articulation point.

Refer to this for detailed implementation: Finding articulation points in ‘O(V + E)’, where ‘V’ is the number of vertices and ‘E’ is the number of edges in the graph.

Let ‘count’ be the number of cities in the ‘GRID’. If the ‘GRID’ contains ‘0’ cities (‘count = 0’), then the answer is ‘0’. If the ‘GRID’ contains only ‘1’ city (‘count = 1’), we can remove this city to make the ‘GRID’ disconnected, so the answer is ‘1’. So, for ‘count <= 1’, the answer is equal to ‘count’.
 

Algorithm:

• Set ‘count = 0’. Use this to count the number of cities in ‘GRID’.
• Run a loop where ‘i’ ranges from ‘0’ to ‘N - 1’:
  • Run a loop where ‘j’ ranges from ‘0’ to ‘M - 1’:
    • ‘count += GRID[i][j]’.
• If ‘count <= 1’, then:
  • Return ‘count’ as the answer.
• Initialize a 2D array ‘seen[n][m]’ and set it to ‘False’. Use it to mark visited cities.
• Set ‘cutPoint = False’. In the DFS traversal, if we find an articulation point, we set ‘cutPoint’ to ‘True’.
• Set ‘count = 0’. Use it to count the number of states in ‘GRID’.
• 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 then we have not visited the city ‘(i, j)’:
      • ‘count += 1’. Increase the number of states.
      • If ‘count > 1’, then the ‘GRID’ is already disconnected:
        • Return ‘0’ as the answer.
      • Cal ‘dfs(i, j)’. If we find an articulation point in the ‘dfs’ function, set ‘cutPoint’ to ‘True’.
• If ‘cutPoint = True’, then there exists at least one articulation point in ‘GRID’:
  • Return ‘1’ as the answer.
• Return ‘2’ as the answer. As the ‘GRID’ cannot be disconnected by removing one city.