Connectivity components; traversal of the graph in depth?

Question

Python

I came across this problem:
Removing cells:
Some cells were removed from a rectangular sheet of checkered paper (M rows, N columns). How many pieces will the rest of the sheet break up into? Two cells do not fall apart if they have a common side.
Specifications Input
The first line contains the numbers M and N, the next M lines - N characters each. If the cell has not been cut out, this corresponds to the # sign, if it is cut out - a dot. 1 <= M, N <= 100.
Output
Print one number.
Examples of
input data
5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####
output
5
My Python solution:
1. Let all '#' characters correspond to vertices numbered from 1 to num_vertex (number of all vertices).
Let's create an array of arrays R, which will store the numbers of vertices and start a counter to count the number of vertices. If R[i][j] = 0, then the element lying on the i-th line in the j-th position is a point (not a vertex), otherwise it is a vertex with the number R[i][j].
2. Create an adjacency matrix vertex_num by vertex_num matrix, where matrix[i][j] = 0 if i is not adjacent to j and 1 if it is. Let's create it this way: we will look at the elements in R and, in certain cases [when an uncut cell borders on other uncut ones (for example, on a line above or below at the same position in the line, or in a given line, but at a position to the left or right) ], we will mark adjacent vertices in matrix. For example, for the input example, the adjacency matrix would look like this:
matrix = 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0]]0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0]]
Each matrix list has 27 elements, since there are 27 '#' characters in total.
3. Create an array of visited elements visited. Next, we will run DFS from the first unvisited element until all elements have been visited, each time increasing the number of connectivity components by 1.
Code:

m,n = map(int,input().split())
R = [[] for i in range(m)]
num_vertex = 0
for i in range(m):
  A = input()
  for j in range(n):
    if A[j] == '#':
      num_vertex += 1
      R[i].append(num_vertex)
    else:
      R[i].append(0)
matrix = [[0]*num_vertex for i in range(num_vertex)]
for i in range(m):
  for j in range(n):
    if R[i][j] != 0:
      if j-1 >= 0 and R[i][j-1] != 0:
        matrix[R[i][j-1]-1][R[i][j]-1],matrix[R[i][j]-1][R[i][j-1]-1] = 1,1
      if j+1 <= n-1 and R[i][j+1] != 0:
        matrix[R[i][j+1]-1][R[i][j]-1],matrix[R[i][j]-1][R[i][j+1]-1] = 1,1
      if i-1 >= 0 and R[i-1][j] != 0:
        matrix[R[i-1][j]-1][R[i][j]-1],matrix[R[i][j]-1][R[i-1][j]-1] = 1,1
      if i+1 <= m-1 and R[i+1][j] != 0:
        matrix[R[i+1][j]-1][R[i][j]-1],matrix[R[i][j]-1][R[i+1][j]-1] = 1,1
visited = [False]*num_vertex
def dfs(start):
  global matrix,visited,num_vertex
  visited[start] = True
  for vertex in range(num_vertex):
    if matrix[start][vertex] == 1 and visited[vertex] == False: dfs(vertex)
num_components = 0
while False in visited:
  dfs(visited.index(False))
  num_components += 1
print(num_components)

And everything would be fine, but only 3 out of 11 tests pass (writes: Error during program execution). Tell me, what could be the error, how can I optimize the algorithm, if possible?

Answer 1

Too lazy to delve into these heaps - a lot of heaped up.

n, m = map(int, input().split())
field = {(x, y) for y in range(n) for x, c in enumerate(input()) if c == '#'}

def dfs(xy):
    field.discard(xy)
    x, y = xy
    for ij in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):
        if ij in field:
            dfs(ij)

res = 0
while field:
    dfs(field.pop())
    res += 1
print(res)