Как алгоритм Дональда Б. Джонсона работает с ограниченной длиной цикла?

Question

Я узнал, что алгоритм, опубликованный в 1975 году Дональдом Джонсоном, является эффективным способом найти все циклы в ориентированном графе. Но теперь у меня есть очень большой график, но мне нужно только найти циклы с ограниченной длиной. Как изменить это, чтобы сделать это?

Answer 1

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