Найти количество избыточных ребер в компонентах графа ⇐ Python

[Anonymous]

Я пытаюсь решить задачу 1319 на Leetcode, которая заключается в следующем:

Есть n компьютеров, пронумерованных от 0 до n - 1, соединенных Соединения кабелей Ethernet, образующие сеть, где Connections = [ai, bi] представляет собой соединение между компьютерами ai и bi. Любой компьютер может напрямую или косвенно подключиться к любому другому компьютеру через сеть.
Вам предоставляются начальные сетевые подключения компьютера. Вы можете извлечь
определенные кабели между двумя напрямую подключенными компьютерами и поместить
их между любой парой отключенных компьютеров, чтобы обеспечить их прямое
подключение.
Возврат минимальное количество раз, которое вам необходимо сделать, чтобы
соединить все компьютеры. Если это невозможно, верните -1.

Подумав немного, я придумал следующий неработающий подход и связанный с ним код:< /p>
Сначала преобразуйте список ребер в список смежности соединений. Подойдите к первому компьютеру и посмотрите, сколько компьютеров доступно с него (например, с помощью DFS). Кроме того, отслеживайте количество соединений, которые неоднократно пытаются получить доступ к посещенному узлу, указывая на то, что есть провод, от которого мы можем избавиться. Это представляет собой связный компонент. Найдите следующий непосещенный узел и повторите тот же процесс. В конце определите, превышает ли количество подсчитанных нами проводов количество подключенных компонентов — 1

Код: Выделить всё

from typing import DefaultDict, List, Set

from collections import defaultdict

class Solution:
def makeConnected(self, n: int, connections: List[List[int]]) -> int:
def dfs(
adj_list: DefaultDict[int, List[int]], computer: int, visited: Set[int]
) -> int:
"""Returns the number of removable wires from this connected component"""

num_removable_wires = 0

stack = [computer]

while len(stack) > 0:
current = stack.pop()

# Already been here, so can remove this wire
if current in visited:
num_removable_wires += 1
continue

visited.add(current)

if current in adj_list:
for neighbor in adj_list[current]:
stack.append(neighbor)

return num_removable_wires

adj_list = defaultdict(list)

for connection in connections:
adj_list[connection[0]].append(connection[1])
# adj_list[connection[1]].append(connection[0])

total_removable_wires = 0
num_components = 0

visited = set()

for computer in adj_list.keys():
if computer in visited:
continue

num_components += 1
total_removable_wires += dfs(adj_list, computer, visited)

# Add computers that are completely isolated
num_components += n - len(visited)

return (
num_components - 1
if total_removable_wires >= num_components - 1
else -1
)

if __name__ == "__main__":
print(Solution().makeConnected(6, [[0, 1], [0, 2], [0, 3], [1, 2]]))

print(
Solution().makeConnected(
11,
[
[1, 4],
[0, 3],
[1, 3],
[3, 7],
[2, 7],
[0, 1],
[2, 4],
[3, 6],
[5, 6],
[6, 7],
[4, 7],
[0, 7],
[5, 7],
],
)
)

Для первого тестового примера этот код работает должным образом. Во-вторых, я понял, что для определенных вершин, например 1, единственными доступными вершинами, прямо или косвенно, являются 4, 3, 7 и 6, поскольку ребра в списке смежности размещаются только в одном направлении. Затем код неправильно определяет, что вершина 0 является частью нового компонента. Чтобы исправить это, я попытался настроить следующее, раскомментировав вторую строку кода при построении списка смежности, чтобы добавить обе стороны одного и того же края:

Код: Выделить всё

for connection in connections:
adj_list[connection[0]].append(connection[1])
adj_list[connection[1]].append(connection[0])

Однако, хотя это исправляет второй тестовый пример, теперь нарушается первый. Теперь, когда код достигает, например, 3 из 0 и видит, что 0 — это уже посещенный сосед, он неправильно заявляет, что ребро избыточно, даже если оно было только что пройдено на пути к 3.
Как мне правильно посчитать количество резервных ребер (или съемных проводов) в контексте этой задачи? Обратите внимание: я понимаю, что на вкладке «Решения Leetcode» есть более эффективные подходы, которые я мог бы реализовать, но мне было интересно, что я делаю неправильно в своей попытке решения и можно ли исправить существующий подход.< /п>

Подробнее здесь: https://stackoverflow.com/questions/787 ... of-a-graph