Я совсем новичок в программировании на Python, изучаю сейчас терию графов и в ходе заданий нужно решить задачу с помощью программирования. Суть задачи - найти количество компонент связности неориентированного графа при помощи поиска в глубину. Даны входные данные:
4 2
1 2
3 2
В качестве выходных даннных должно быть число компонент связности (в данном случае 2).
(Первая строка - кол-во вершин в графе, кол-во граней, вторая и третья строки - пары вершин, соединенных ребрами).
Прошу помощи!
(………..)
Так… собственными усилиями корректный код написан. Как переписать решение, чтобы данные из списка смежностей брались из готового файла? (Как в задачах на олимпиадное программирование). Заранее спасибо.
Вот исходный код:
g = [ 1: [2], 2: [1, 3], 3: [2], 4: [ ] ] def Answer(G): visited = set() k = 0 def dfs(x): visited.add(x) for y in G[x]: if y not in visited: dfs(y) for v in G: if v not in visited : k += 1 dfs(v) return k print (Answer(G))