Почему это работает
- Стрелка x → y с весом k значит x / y = k, а обратная — y / x = 1 / k. Вдоль пути дроби сокращаются: (p / r) × (r / s) = p / s, поэтому произведение весов и есть ответ.
- Поиск в глубину пробует стрелки по одной; ветка, из которой до end не дойти, как u здесь, возвращает -1, и обход идёт по следующей стрелке. visited не даёт ходить по кругу.
- В графе есть только переменные из уравнений, поэтому запрос про любую другую — сразу -1.
Сложность
Время O(q × (n + m)), где n — число переменных, m — уравнений, q — запросов: каждый запрос — один обход, который заходит в переменную не больше одного раза. Память O(n + m) на граф и visited.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗