Неправильно написан алгоритм BFS

Question

Дана следующая задача:

Алхимики средневековья владели знаниями о превращении различных химических веществ друг в друга. Это подтверждают и недавние исследования археологов.

В ходе археологических раскопок было обнаружено m глиняных табличек, каждая из которых была покрыта непонятными на первый взгляд символами. В результате расшифровки выяснилось, что каждая из табличек описывает одну алхимическую реакцию, которую умели проводить алхимики.

Результатом алхимической реакции является превращение одного вещества в другое. Задан набор алхимических реакций, описанных на найденных глиняных табличках, исходное вещество и требуемое вещество. Необходимо выяснить: возможно ли преобразовать исходное вещество в требуемое с помощью этого набора реакций, а в случае положительного ответа на этот вопрос — найти минимальное количество реакций, необходимое для осуществления такого преобразования. Входные данные

Первая строка входного файла INPUT.TXT содержит целое число m (0 ≤ m ≤ 1000) – количество записей в книге. Каждая из последующих m строк описывает одну алхимическую реакцию и имеет формат вещество1 -> вещество2, где вещество1 – название исходного вещества, вещество2 – название продукта алхимической реакции. m+2-ая строка входного файла содержит название вещества, которое имеется исходно, m+3-ая – название вещества, которое требуется получить.

Во входном файле упоминается не более 100 различных веществ. Название каждого из веществ состоит из строчных и заглавных английских букв и имеет длину не более 20 символов. Строчные и заглавные буквы различаются. Выходные данные

В выходной файл OUTPUT.TXT выведите минимальное количество алхимических реакций, которое требуется для получения требуемого вещества из исходного, или -1, если требуемое вещество невозможно получить.

Ссылка на задачу и примеры входных и выходных данных здесь

Я пишу следующий код:

from collections import defaultdict


class Graph:
    def __init__(self):
        self.graph = defaultdict(list)

    def addEdge(self, u, v):
        self.graph[u].append(v)

    def bfs(self, s, f, n):
        level = [-1] * n
        queue = [s]
        level[s] = 0
        while queue:
            node = queue.pop(0)
            try:
                l = list(self.graph[node])
                for child in l:
                    if level[child] == -1:
                        queue.append(child)
                        level[child] = level[node] + 1
            except KeyError:
                continue
        return level[f]


data = open('input.txt', 'r')
file = open('output.txt', 'w')

n = int(data.readline())
g = Graph()
names = []

for i in range(n):
    line = data.readline().split()
    a, _, b = map(str, line)
    if a in names:
        a = names.index(a)
    else:
        names.append(a)
        a = len(names) - 1
    if b in names:
        b = names.index(b)
    else:
        names.append(b)
        b = len(names) - 1
    g.addEdge(a, b)

s = data.readline().split()[0]
if s in names:
    s = names.index(s)
else:
    file.write('0')
    file.close()
    exit()
f = data.readline().split()[0]
if f in names:
    f = names.index(f)
else:
    file.write('-1')
    file.close()
    exit()
file.write(str(g.bfs(s, f, n)))
file.close()

Граф создаётся как словарь в виде списка смежности, а сама задача решается с помощью обхода в глубину. Но она валится на 7м тесте. :( Что в коде неправильно написано?

БЛОГ НА HUSL

Неправильно написан алгоритм BFS

Ответы (0 шт):