Можете подсказать, как находить нужные пути в графе?
В первую очередь, нужно найти пути, которые между собой не соприкасаются. Если такие есть, то ответ 0.
Если таких путей нет, то нам нужно найти путь, в котором LCA между желтым и синим волшебником будет находится ближе всего к корню.
Были идеи с BFS 0-1, но из-за большего количества подобных путей, этот бфс оказывается неправильным.
Что такое корень? Что такое LCA в графе?
Под корнем я имею ввиду столицу, а насчет LCA. Самый оптимальный путь, который ведет желтого и синего волшебника в столицу, будет являться деревом(ну или бамбук). Так что на нем мы будем искать LCA.
Разве самый оптимальный путь, может хранить в себе циклы?
А да, может. Мой косяк.
Если оставить только ребра которые есть у желтого колдуна или синего колдуна то это не обязательно будет дерево
Подумай про мосты в графе.
Попробуй превратить город в дерево поделив его на компоненты двусвязности. Затем уже можно будет находить LCA
это что?
Компонентой двусвязности графа называется такое максимальное подмножество из трех или более его вершин, в котором любые две вершины соединены, по крайней мере, двумя путями, не имеющими общих ребер
Если так подумать та же самая компонента сильной связанности просто в неориентированом графе с небольшими отличиями
как такое деление будет работать в полном графе?
Имеешь ввиду если два волшебника в разных компонентах?
А если приходит запрос с вершиной из компоненты двусвязности и с вершиной, не находящийся в ней?
Может быть такое что при делении графа останутся вершины не входящие ни в одну компоненту в таком случае их можно взять как отдельный компонент
я имею ввиду, что если приходит запрос на две вершины и они находятся в разных “компонентах”, тогда изначально нам нужно подсчитать кратчайший путь выхода из компоненты для всех компонент двусвязности, после находить LCA и какой-нибудь dp-шкой находить ответ?
Насколько я понял, если решать мостами, то там ± выйдет тоже самое, что и если мы будем использовать “компоненты двусвязности”?
Нееее, из этих компонент создай дерево затем при запросе найди в каких компонентах находятся данные вершины. Допустим они в компонентах A и B. Тогда берешь LCA из этих вершин уже в новом дереве которое ты построил(легче говоря конденсация только в неориентированом графе) и просто уже от этого общего предка находишь сколько ребер от него до компонента в котором находится штаб F. Забыл упомянуть что компонента где находится F должна быть корнем
А чем мое решение отличается от твоего🤔
а нам же нужно находить кратчайшее расстояние в компоненте, т.к. на пути от LCA до корня мы можем наткнуться на такую компоненту, выход из которой нам необходим именно кратчайший
Смысл тебе в минимальном пути, главное минимальное количество общих дорог. В компоненте двусвязности у тебя по любому будут двое разных путей, они могут пересекаться в вершинах но не в ребрах
И из этих 2 путей нам нужен с самым минимальным кол-вом городов от начало компоненты к концу. Если мы по любому из них пройдем, то может быть такой, что мы покрасили больше дорог, чем могли, если бы прошли по другому путю
Условно, это наша компонента, Она имеет 2 пути, но по длине они разные, так что нам нужно самое короткое. Так что распределив компоненты двусвязности, нам нужно посчитать кратчайшее расстояние от начала компоненты, до ее конца.
Либо я чего то не понимаю либо не знаю. Нам нужен еще и кратчайший путь?
