Первое, что приходит на ум, это использовать DFS следующим образом:
DFS начинается с некоторой вершины v1 и «открывает» вершины одну за другой. Каждая обнаруженная вершина рекурсивно запускает свою собственную DFS и «обрабатывается» после возврата рекурсии.
Давайте предположим, что есть два направленных пути от v1 до v2. В этом случае v2 будет «обнаружен» (посредством одного из этих двух путей, идущих от v1 до v2) и в конечном итоге «обработан». Однако рекурсия v1 еще не закончена. Поток DFS достигнет v2 во второй раз (на этот раз с использованием второго пути от v1 до v2), но на этот раз v2 уже находится в «обработанном» состоянии.
Поэтому всякий раз, когда мы сталкиваемся с «обработанной» вершиной, это подразумевает, что к ней идет второй путь.
Этот метод работает для всех видов ориентированных графов, он не использует тот факт, что граф сильно связан, поэтому, возможно, этот факт можно было бы использовать для более оптимального решения.
Также обратите внимание, что для неориентированных графов ситуация гораздо более расслабленная - нам просто нужно обнаружить все циклы в графе, и каждая пара вершин в цикле будет иметь два пути между ними. В ориентированном графе цикл является односторонним, поэтому мы не можем предполагать двойной путь между членами цикла.