Алгоритм проверки, сильно ли связан направленный граф
После этой строки:
qty = scan.nextInt();
Всегда добавляйте еще одну строку для очистки сканера:
scan.nextLine();
Кроме того, используйте
sc.nextLine();
вместо
sc.next();
4 ответа
Алгоритм сильно связанных компонентов Тарьяна (или вариант Габоу ), конечно, будет достаточным; если есть только один компонент с сильной связью, то граф сильно связан.
Оба являются линейным временем.
Как и при обычном поиске в глубину, вы отслеживаете состояние каждого узла: новый, видимый, но еще открытый (он в стеке вызовов), просмотрено и завершено. Кроме того, вы сохраняете глубину, когда вы впервые достигли узла, и самую низкую такую глубину, которая доступна из узла (вы узнаете это после того, как закончите узел). Узел является корнем сильно связного компонента, если наименьшая достижимая глубина равна его собственной глубине. Это работает, даже если глубина, на которую вы достигаете узла от корня, не является минимально возможной.
You can calculate the All-Pairs Shortest Path and see if any is infinite.
Алгоритм Тарьяна уже упоминался. Но обычно мне легче следовать алгоритму Косараджу , несмотря на то, что он требует двух обходов графа. IIRC, это также довольно хорошо объяснено в CLRS.
Один из способов сделать это - создать матрицу лапласа для графа, затем вычислить собственные значения и, наконец, подсчитать количество нулей. Граф является сильно связным, если существует только одно нулевое собственное значение.
Примечание: обратите внимание на несколько иной метод создания матрицы Лапласа для ориентированных графов.