График - сильно связанные компоненты

Question

Есть ли какой-нибудь быстрый способ определить размер самого большого сильно связанного компонента на графике?

Я имею в виду, что очевидный подход будет означать определение каждого SCC (можно сделать, используя два DFSзвонки, я полагаю), а затем перебирая их и беря максимум.

Я почти уверен, что должен быть какой-то лучший подход, если мне нужен только размер этого компонента и только самый большой,но я не могу придумать хорошего решения.Есть идеи?

Спасибо.

Answer 1

Позвольте мне ответить на ваш вопрос другим вопросом -
Как определить, какое значение в наборе является наибольшим, не изучая все значения?

Answer 2

Во-первых, вы можете использовать Алгоритм Тарьяна , для которого требуется только одна DFS вместо двух. Если вы четко понимаете алгоритм, SCC образуют DAG, и этот алгоритм находит их в обратном топологическом порядке сортировки. Поэтому, если у вас есть представление о графике (например, визуальное представление), и если вы знаете, что относительно большие SCC возникают в конце DAG, вы можете остановить алгоритм, как только обнаружите первые несколько SCC.