Хелпаните, уже неделю сижу.

Парни, хелп. Уже неделю не могу понять как решить эту задачку.

http://matol.kz/comments/4113/show

Для заданного графа выделяешь компоненты сильной связности (это называется конденсация). Для каждой компоненты ведешь подсчет количества вершин с "высоким статусом". При подсчете путей для заданной дороги смотришь, дорога лежит между компонентами или нет. Если нет, т. е. дорога находится в компоненте, то ответ сразу ноль будет. Если между, то выбираешь компоненты, которые находятся по разные стороны от дороги, слева и справа, считаешь суммарное число городов с высоким статусом с этих компонент, произведение полученных двух чисел будет ответом.

По идее, самое сложное - провести конденсацию графа, но в интернете должно быть много примеров этого алгоритма.

UPD. Так как граф может быть не связным, нужно еще искать нужный подграф сначала

Moon-chan сказал(а):↑

Для заданного графа выделяешь компоненты сильной связности (это называется конденсация). Для каждой компоненты ведешь подсчет количества вершин с "высоким статусом". При подсчете путей для заданной дороги смотришь, дорога лежит между компонентами или нет. Если нет, т. е. дорога находится в компоненте, то ответ сразу ноль будет. Если между, то выбираешь компоненты, которые находятся по разные стороны от дороги, слева и справа, считаешь суммарное число городов с высоким статусом с этих компонент, произведение полученных двух чисел будет ответом.

По идее, самое сложное - провести конденсацию графа, но в интернете должно быть много примеров этого алгоритма.

Нажмите, чтобы раскрыть...

Я уже понял, что задача решается через графы, но я с ними знаком только в теории, знаю алгоритм обхода в глубину (dfs), но как применить это не понимаю

max0120842 сказал(а):↑

Я уже понял, что задача решается через графы, но я с ними знаком только в теории, знаю алгоритм обхода в глубину (dfs), но как применить это не понимаю

Нажмите, чтобы раскрыть...

Тут поиск компонент сильной связности проводить нужно

Moon-chan сказал(а):↑

Тут поиск компонент сильной связности проводить нужно

Нажмите, чтобы раскрыть...

В разве компоненты сильной связности могут существовать с неориентированном графе? у нас по заданию ведь он неориентированный

 

 

max0120842 сказал(а):↑

В разве компоненты сильной связности могут существовать с неориентированном графе? у нас по заданию ведь он неориентированный

Нажмите, чтобы раскрыть...

Да. Неориентированный граф вообще можно считать частным случаем ориентированного

Moon-chan сказал(а):↑

Да. Неориентированный граф вообще можно считать частным случаем ориентированного

Нажмите, чтобы раскрыть...

Ты сверхразум?