Как узнать, существует ли путь от одного SCC к другому?
Для графа, после нахождения сильно связанных компонентов, как найти количество SCC, которые имеют путь друг к другу? Я хочу найти, если есть путь к SCC2 от SCC1.
3 ответа
Вы спросили две вещи:
Как найти количество SCC, которые имеют путь друг к другу?
Вы можете запускать dfs из каждого SCC и сохранять те, к которым вы можете обратиться.
Например: вы запускаете dfs из SCC A, и вы можете достичь SCC B и C. (Просто проверьте, что такое SCC узла, который вы посещаете). Затем вы запускаете dfs из другого SCC D, и вы достигаете SCC A. В это время Вы можете остановить свои DFS, потому что вы уже рассчитали, каковы другие.
Таким образом, сложность времени O(n+m)
Предполагая, что вам нужно только знать, достижим ли SCC от другого или нет (true/false), вы можете назначить идентификатор каждому SCC, пока вы его обнаружите, и создать сопоставление для каждого узла, которому принадлежит SCC_ID. Затем снова просмотрите исходный график. Если существует край (u,v) где SCC_ID(u) != SCC_ID(v) тогда SCC достижим от другого.
Подобный тип вопроса: Алгоритм Косараю для поиска SCC, но отслеживать границу между SCC?
При нахождении SCC с использованием Kosaraju (потому что это легко реализовать) назначьте каждому обнаружителю SCC, также известному как представитель, уникальный идентификатор, а для каждого SCC назначьте его идентификатор всем его членам. Это поможет запомнить, какой участник к какому SCC принадлежит. Теперь эта информация может помочь нам сжать этот граф в граф, узлы которого являются SCC (репрезентативным идентификатором). При построении этого графика сжатия вы будете знать, какой SCC к какому подключен.
Вы можете обратиться к этой ссылке для получения более подробной информации вместе с реализацией: https://cp-algorithms.com/graph/strongly-connected-components.html.