Нужен ли этот шаг раньше

Средняя

Рецепт состоит из n шагов с номерами от 0 до n - 1. Пара [a, b] в списке steps означает, что шаг a должен быть выполнен раньше шага b. Циклов в зависимостях нет. Зависимость может быть и косвенной: если a нужен раньше b, а b раньше c, то и a нужен раньше c. Дан список вопросов questions, где questions[j] = [u, v] спрашивает: обязательно ли выполнить шаг u раньше шага v (напрямую или через цепочку)? Верните список ответов True / False в том же порядке.

Пример 1

n=4, steps=[[2, 0], [0, 3]], questions=[[2, 3], [3, 2], [1, 0]] → [True, False, False]

Шаг 2 идёт раньше 0, а 0 — раньше 3, значит 2 нужен для 3 (через 0). Обратное неверно, а шаг 1 ни с чем не связан.

Пример 2

n=3, steps=[], questions=[[0, 1], [2, 1]] → [False, False]

Зависимостей нет вовсе, поэтому на оба вопроса ответ «нет».

Пример 3

n=5, steps=[[4, 3], [3, 1], [1, 0], [4, 2]], questions=[[4, 0], [2, 0], [3, 4]] → [True, False, False]

Ограничения

2 ≤ n ≤ 100
0 ≤ len(steps) ≤ n·(n − 1) / 2
steps[i] = [a, b], 0 ≤ a, b < n, a ≠ b, все пары различны
В зависимостях нет циклов
1 ≤ len(questions) ≤ 10⁵
questions[j] = [u, v], 0 ≤ u, v < n, u ≠ v

Встречал эту задачу на настоящем собесе?

Решили0

Пробовали0

Отправок0

Принято—

Темы

Depth-First Search Breadth-First Search Graph Topological Sort

Вход

n=4, steps=[[2, 0], [0, 3]], questions=[[2, 3], [3, 2], [1, 0]]

Ожидается

[True, False, False]

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 180 тестов на сервере, включая скрытые.