Посчитать количество компонент связности графа и вывести их
Дан неориентированный невзвешенный граф. Необходимо посчитать количество его компонент связности и вывести их.
Входные данные
Во входном файле записано два числа N и M (0
Выходные данные
В первой строчке выходного файла выведите количество компонент связности. Далее выведите сами компоненты связности в следующем формате: в первой строке количество вершин в компоненте, во второй — сами вершины в отсортированном порядке.
Здравствуйте! Написал вот такой код:
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 48
class Solution: def __init__(self, n, used, g): self.n = n self.used = used self.g = g self.p = [] self.answer = [] def dfs(self, v): self.used[v] = True self.p.append(v) for u in self.g[v]: if not self.used[u]: self.dfs(u) def number_of_comps(self): ans = 0 self.answer = [] for v in range(self.n): if not self.used[v]: ans += 1 self.dfs(v) self.answer.append(self.p[:]) self.p.clear() return ans def comps(self): return self.answer def main(): n, m = map(int, input().split()) g = [[] for j in range(n)] used = [False] * n for i in range(m): x, y = map(int, input().split()) g[x - 1].append(y - 1) g[y - 1].append(x - 1) answer = Solution(n, used, g) print(answer.number_of_comps()) g.clear() used.clear() for i in list(filter(lambda x: len(x) > 0, answer.comps())): print(len(i)) print(*sorted(list(map(lambda x: x + 1, i)))) main()
Но он не проходит 16 тест (входные данные неизвестны) выдает ошибку исполнения. Помогите пожалуйста найти место в котором может происходить ошибка.
Определение связности графа
Есть вопрос как определить связен ли граф? А если не связан, то выделить компоненты связности
на вход дается количество вершин и ребер (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
Проверить, является ли graph сильно связанным или нет
Учитывая ориентированный graph, проверьте, является ли он сильно связным или нет. Ориентированный graph называется сильно связным, если каждая его вершина достижима из любой другой вершины.
Например, следующий graph сильно связан, поскольку существует путь между всеми парами вершин:
Простое решение — выполнить Поиск в глубину (DFS) или же Поиск в ширину (BFS) начиная с каждой вершины Graph. Если каждый вызов DFS/BFS посещает все остальные вершины Graph, то граф сильно связан.
Алгоритм может быть реализован следующим образом на C++, Java и Python:
C++
результат:
The graph is strongly connected
Java
результат:
The graph is strongly connected
Python
edges = [ ( 0 , 4 ) , ( 1 , 0 ) , ( 1 , 2 ) , ( 2 , 1 ) , ( 2 , 4 ) , ( 3 , 1 ) , ( 3 , 2 ) , ( 4 , 3 ) ]
результат:
The graph is strongly connected
Временная сложность приведенного выше решения равна O(n × (n + m)) , куда n это общее количество вершин и m — общее количество ребер в Graph.
Можем ли мы сделать лучше?
Мы можем сказать, что G сильно связна, если:
- DFS(G, v) посещает все вершины Graph G , то существует путь из v к каждой другой вершине в G , а также
- Существует путь из любой другой вершины в G к v .
За G быть сильно связанным, путь от x —> y а также y —> x должно существовать для любой пары вершин (x, y) на Graphе.
Если пункты 1 и 2 верны, мы можем достичь x —> y идя от вершины x к вершине v (из п. 2), а затем из вершины v к вершине y (из ч. 1).
Точно так же мы можем достичь y —> x идя от вершины y к вершине v (из п. 2), а затем из вершины v к вершине x (из ч. 1).
- Начинать DFS(G, v) из случайной вершины v Graphа G . Если DFS(G, v) не может достичь каждой другой вершины в Graph G , то есть некоторая вершина u , такой, что нет направленного пути из v к u . Таким образом, G не сильно связан. Если он достигает каждой вершины, то существует направленный путь из v к любой другой вершине Graph G .
- Реверс направления всех ребер в ориентированном Graph G .
- Снова запустите DFS, начиная с вершины v . Если DFS не может достичь каждой вершины, то существует некоторая вершина u , что в исходном Graph нет направленного пути из u к v . С другой стороны, если он достигает каждой вершины, то существует направленный путь из каждой вершины. u к v в исходном Graphе.
Если G проходит обе DFS, сильно связано. Алгоритм может быть реализован следующим образом на C++, Java и Python:
Проверьте, является ли graph сильно связанным или не использует один обход DFS.
Учитывая ориентированный graph, проверьте, является ли он сильно связным или нет. Ориентированный graph называется сильно связным, если каждая его вершина достижима из любой другой вершины.
Например, следующий graph сильно связан, поскольку существует путь между всеми парами вершин:
в предыдущий пост, мы обсудили решение, которое требует двух DFS обходы Graph. Мы можем проверить, является ли граф сильно связным или нет, выполнив только один обход DFS на Graph.
Когда мы делаем поиск в глубину из вершины v в ориентированном Graph может быть много ребер, выходящих из его поддерева. Когда мы говорим, что поддерево имеет корни в v , мы имеем в виду все v’s потомков, включая саму вершину. Ребра, выходящие из поддерева, будут либо задним ребром, либо поперечным ребром. Передние ребра не могут выходить из поддерева, поскольку они могут только входить в поддерево, или, если они начинаются внутри поддерева, они будут проходить только внутри поддерева.
Можно сказать, что graph сильно связен тогда и только тогда, когда для каждого ребра u —> v в Graph есть хотя бы одно обратное или поперечное ребро, выходящее из поддерева с корнем v .
Как мы должны изменить DFS, чтобы мы могли проверить, есть ли исходящие ребра из каждого поддерева?
Мы можем изменить DFS так, чтобы DFS(v) возвращает наименьшее время прибытия, к которому существует выход из поддерева с корнем v . Например, пусть arrival(v) быть временем прибытия вершины v в ДФС. Тогда, если существует ребро вне поддерева с корнем v , это к чему-то побывало раньше v и, следовательно, с меньшим значением прихода.
Помните, что для задней кромки или поперечной кромки, u —> v , arrival[u] > arrival[v] .
Предположим, что из поддерева с корнем в точке исходят четыре ребра. v к вершине a , b , c , а также d с временем прибытия arrival(a) , arrival(b) , arrival(c) , а также arrival(d) , соответственно. Смотрим на их времена прихода и рассматриваем самые маленькие среди них. Это будет значение, возвращаемое DFS(v) , т.е. DFS(v) возвращает минимум min из arrival(a), arrival(b), arrival(c) а также arrival(d) . Но прежде чем вернуться, мы должны проверить, что min меньше, чем arrival(v) . Если min меньше, чем arrival(v) , то это означает, что по крайней мере одно обратное или поперечное ребро выходит из поддерева с корнем в v . Если нет, то можно остановить процедуру и сказать, что graph не является сильно связным.
Это показано ниже на C++, Java и Python: