Компоненты связности; обход графа в глубину?

Question

[William03]

Наткнулся на такую задачу:
Удаление клеток:
Из прямоугольного листа клетчатой бумаги (M строк, N столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.

Входные данные
В первой строке находятся числа M и N, в следующих M строках - по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана - точка. 1 <= M, N <= 100.

Выходные данные
Вывести одно число.

Примеры
входные данные
5 10
##..#####.
.#.#.#....
###..##.#.
..##.....#
.###.#####
выходные данные
5
Мое решение на Python:
1. Пусть все символы '#' соответствуют вершинам, пронумерованным от 1 до num_vertex (число всех вершин).
Создадим массив массивов R, в котором будет хранить номера вершин и заведем счетчик, чтобы посчитать количество вершин. Если R[i][j] = 0, то элемент, лежащий на i-й строке в j-й позиции является точкой (не вершиной), а иначе это вершина с номером R[i][j].
2. Создадим матрицу смежности vertex_num на vertex_num matrix, где matrix[i][j] = 0, если вершина i не смежна с вершиной j и 1, если смежна. Создадим ее таким образом: будем просматривать элементы в R и, в определенных случаях [когда невырезанная клетка граничит с другими невырезанными(например, на строке выше или ниже при той же позиции в строке, или в данной строке, но на позиции слева или справа)], будем отмечать в matrix смежные вершины. Например, для примера на входе матрица смежности будет выглядеть так:
matrix = [[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, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 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, 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, 1, 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, 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, 0, 0, 0, 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, 0, 0, 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, 0, 0, 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, 0, 0, 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, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 1, 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, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 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, 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, 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, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 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, 0, 0, 0, 0, 0, 0, 1], [0, 0, 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], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 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, 1, 0, 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, 0, 0, 0, 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, 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]]
В каждом списке матрицы по 27 элементов, поскольку всего символов '#' 27.
3. Создадим массив visited посещенных элементов. Далее будем запускать DFS от первого непосещенного элемента, пока все элементы не будут посещены, каждый раз увеличивая кол-во компонент связности на 1.
Код:

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)

И все бы ничего, но проходит только 3 теста из 11 (пишет: Ошибка во время исполнения программы). Подскажите, в чем может быть ошибка как можно оптимизировать алгоритм, если возможно?

Comments

[Roman K]

Неприлично такую мешанину на публику выкладывать

[William03]

Вопрос в том, что за ошибка может быть. До меня не доходит. Ведь матрица же есть, dfs корректный вроде.

Answer 1

[longclaps]

Лень копаться в этих нагромождениях - сильно много наворочено.

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)

Comments

[William03]

6/11 тестов. Но спасибо и за это решение. Я все равно его буду разбирать.

[longclaps]

William03, предъявите тесты или проверочную систему.

[longclaps]

William03, нагуглил вашу задачу. Падает по переполнению стека. А вот так не падает:

from sys import setrecursionlimit

setrecursionlimit(100500)
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)

[William03]

longclaps, Точно! Благодарю!!!