многопоточный алгоритм для обнаружения циклов в ориентированном графе

Я ищу параллельный алгоритм, который помог бы мне в обнаружении циклов в ориентированном графе.

Я знаю, что последовательный алгоритм использует поиск в глубину с раскрашиванием, однако я думаю, что он не будет работать в многопоточной среде. Один пример ориентированного графа для иллюстрации:

A->(B, C), B->(D), D->(E), C->(E), E->(F)

                         A
                        / \
                       B   C
                       |   |
                       D   |
                        \ /
                         E
                         |
                         F

(Надеюсь, из вышеизложенного понятно.Все ребра в графе расположены сверху вниз)

Для приведенного выше ориентированного графа во время параллельного выполнения возможно следующее выполнение.

(предполагаемая мной цветовая схема: белый — непосещенный, серый — выполнение dfs не завершено и черный — завершенное выполнение и посещение)

Dfs(B) по потоку 1, который в конечном итоге окрашивает E в серый цвет и выполняет dfs (E) (ведущий к F). Прежде чем это будет завершено, поток 2 выполняет dfs(C). Он понимает, что E серый, и сообщает о цикле, который, очевидно, не соответствует действительности.

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

Не мог бы кто-нибудь помочь мне с этим?

Спасибо.