Привет!

Не получается придумать оптимальное решение для следующей задачи: дан ориентированный граф (городов), вершины пронумерованы по DFS (pre-order).

Говорим, что город w снабжает город v, если все пути из корня (вершины 1) в v проходят через w.

Для каждого города нужно посчитать количество городов, которые он снабжает. Всего городов 1000, дорог (однонаправленных рёбер) 2000. Решить можно в лоб, перечисляя все пути через BFS или DFS, но это экспонента, не годится.

Думал о всяких рекурсивных методах, имея в виду такое наблюдение: если город w не снабжает город v, то он не снабжает и всех потомков v.