Почему мой код поиска моста DFS возвращает неверные веса моста? ⇐ Python

[Anonymous]

Я пытаюсь перевести алгоритм графа C++ на Python.

Версия C++ находит все ребра моста в неориентированном графе, используя DFS Тарьяна (значения с низким уровнем связи).
Мой код Python должен собирать веса всех ребер моста, сортировать их и вычислять две суммы (

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

sum_max

и sum_min), взяв чередующиеся элементы из отсортированного списка.
Однако для некоторых входных данных выходные данные Python не совпадают с выходными данными C++.
Вот соответствующая часть моего кода Python:

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

g = [[] for _ in range(N)]
vis = [False] * N
disc = [0] * N
low = [0] * N
a = [0] * N
bridgeEdge = []
tim = 0

def dfs(node, par):
global tim
vis[node] = True
tim += 1
disc[node] = low[node] = tim

for nxt, idx in g[node]:
if nxt == par:
continue
if not vis[nxt]:
dfs(nxt, node)
if low[nxt] > disc[node]:
bridgeEdge.append(a[idx])
low[node] = min(low[node], low[nxt])
else:
low[node] = min(low[node], disc[nxt])

После запуска DFS, начиная с узла 1, я сортирую BridgeEdge и вычисляю:

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

bridgeEdge.sort()

sum_max = sum(bridgeEdge[i] for i in range(len(bridgeEdge)-1, -1, -2))
sum_min = sum(bridgeEdge[i] for i in range(len(bridgeEdge)-2, -1, -2))

Проблема
Мои выходные данные Python отличаются от версии C++, когда граф отключен или когда ребра образуют циклы.
Вопросы

• Отсутствует ли в моей реализации DFS необходимое условие из кода C++?
• Должен ли я нужно запускать dfs() на всех непосещенных узлах, а не только на dfs(1, -1)?
• Есть ли специфичная для Python проблема, связанная с глубиной рекурсии или глобальным доступом, которая может повлиять на результат?

Любая помощь приветствуется!

Подробнее здесь: https://stackoverflow.com/questions/798 ... ge-weights