Компоненты связности; обход графа в глубину?
Наткнулся на такую задачу:
Удаление клеток:
Из прямоугольного листа клетчатой бумаги (M строк, N столбцов) удалили некоторые клетки. На сколько кусков распадётся оставшаяся часть листа? Две клетки не распадаются, если они имеют общую сторону.
Входные данные
В первой строке находятся числа M и N, в следующих M строках — по N символов. Если клетка не была вырезана, этому соответствует знак #, если вырезана — точка. 1
Выходные данные
Вывести одно число.
Примеры
входные данные
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 = 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 И все бы ничего, но проходит только 3 теста из 11 (пишет: Ошибка во время исполнения программы). Подскажите, в чем может быть ошибка как можно оптимизировать алгоритм, если возможно?
Простой 2 комментария
Определение связности графа
Есть вопрос как определить связен ли граф? А если не связан, то выделить компоненты связности
на вход дается количество вершин и ребер (n и m) а после m строк описывающих ребра (матрица смежности наверное зовется).
Нет идей как вообще это можно реализовать.
Буду рад любой помощи
Посчитать количество компонент связности графа
Дан неориентированный невзвешенный граф. Необходимо посчитать количество его компонент связности и.
Подсчитать количество компонент связности графа
Всем привет, есть задача, которую я решил на с++, а надо на питоне, может кто-нибудь помочь.
Определение связности графа
Определить, является ли связанным заданный граф. (использовать рекурсивную процедуру проверки.
Определение связности графа
Добрый день! столькнулся с задачей определения связанности графа, исходные данные вершина -.
Сообщение от nubik53 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47
def gcc(graph,vert): # Перечисление компонент связности def dfs(curr,comp): # Обход в глубину chk[curr]=1 for pair in graph: if pair[0]==curr: v=pair[1] if chk[v]==0: comp.append(v) dfs(v,comp) if pair[1]==curr: v=pair[0] if chk[v]==0: comp.append(v) dfs(v,comp) else: return chk=[0 for _ in range(vert)] ncomp=0 while True: for a,v in enumerate(chk): if v==0: comp=[a] dfs(a,comp) ncomp+=1 print("Компонента содержит вершины:",comp) break else: break print("Найдено компонент связности: ",ncomp) # Ввод графа n=int(input()) m=int(input()) graph=[] for _ in range(m): a1,a2=map(int,input().split(",")) graph.append((a1,a2)) gcc(graph,n)
8 9 0,1 0,2 1,2 1,3 2,3 3,4 4,5 5,6 5,7 Компонента содержит вершины: [0, 1, 2, 3, 4, 5, 6, 7] Найдено компонент связности: 1
8 8 0,1 0,2 1,2 1,3 2,3 3,4 5,6 5,7 Компонента содержит вершины: [0, 1, 2, 3, 4] Компонента содержит вершины: [5, 6, 7] Найдено компонент связности: 2
Число компонент связности
Задача:
Дан неориентированный невзвешенный граф. Необходимо посчитать количество его компонент связности и вывести их. Во входном файле записано два числа N и M (0 < N ≤ 100000, 0 ≤ M ≤ 100000). В следующих M строках записаны по два числа i и j (1 ≤ i, j ≤ N), которые означают, что вершины i и j соединены ребром.
В первой строчке выходного файла выведите количество компонент связности. Далее выведите сами компоненты связности в следующем формате: в первой строке количество вершин в компоненте, во второй - сами вершины в порядке возрастания.
Пример:
Входные данные:
6 4
3 1
1 2
5 4
2 3
Выходные данные:
3
3
1 2 3
2
4 5
1
6
Код написал, но на определенном этапе превышает ограничение по времени (на 0.069 сек)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43
inp =list(map(int,input().split())) n,m = inp[0],inp[1] def ToDict(n,m): ribs = list() while m > 0: ribs.append(list(map(int, input().split()))) m -= 1 ribsDict = dict() for i in range(n): currRibs = [] for j in range(len(ribs)): if ribs[j][0] == i + 1: currRibs.append(ribs[j][1]) elif ribs[j][1] == i + 1: currRibs.append(ribs[j][0]) ribsDict[i + 1] = currRibs return ribsDict ribsDict = ToDict(n,m) Visited = [False]*(n + 1) def DFS(start,verts): Visited[start] = True verts.append(start) for u in ribsDict[start]: if not Visited[u]: DFS(u,verts) return verts comps = list() for i in range(1,n+1): if not Visited[i]: comps.append(DFS(i,list())) print(len(comps)) for i in range(len(comps)): print(len(comps[i])) print(' '.join(list(map(str,sorted(comps[i])))))