ближайший узел встречи двух заданных узлов в ориентированном графе

Мне дан Направленный граф, и в нем есть два узла, мне нужно найти ближайший узел, к которому можно добраться из обоих. Единственная проблема в том, что я могу сделать это с двумя dfs, но мне сказали сделать это в O (logn). Дополнительным ограничением является то, что каждая ячейка может иметь максимум один исходящий край. Входные данные представлены в виде массива размера N, где eachentry в массиве обозначает индекс узла, к которому ведет этот узел. Так что это код, который я пробовал (не совсем DFS, но все же):

int leastCommonDescendent(int nodes[], int N, int node1, int node2)
{
int *visited = new int [N];
int cnt1 = 0; //used for counting length of path from node1 to node2
int cnt2 = 0; //used for counting length of path from node2 to node1
int mark = node1; //storing as a marker needed later for detecting end of search

if(node1 == node2) return node2;
for(int i = 0; i < N; i++){
visited[i] = 0;
}

while((nodes[node1] != node1) && (nodes[node1] != -1) && (visited[node1] == 0) && (node1 != node2)){
visited[node1]++;
node1 = nodes[node1];
cnt1++;
}

visited[node1]++; //so that first node in cycle has count 2
//if find a node in 2nd iteration that has count 2
//such that when node1 == node2 it means we are in the same subgraph
//elsif node1 != node2 we are in different sub graphs

while((nodes[node2] != node2) && (nodes[node2] != -1) && (visited[node2] != 2) && (node1 != node2)){
visited[node2]++;
node2 = nodes[node2];
cnt2++;
}
//In below case the nodes are in different disjoint subgraphs
//and both subgraphs have loops so node1 can never be equal to node2
//cout << visited[node1] << visited[node2] << endl;
if(node1 != node2) return -1;
//In below case both nodes are in different disjoint subgraphs
//but there is no loop in 1st one(containing node1)
//and 2nd one has a loop
if ((nodes[node1] == -1) && (visited[node2] == 1)) return -1;
//In below case both nodes are in different disjoint subgraphs
//but 1st one has a loop and second one doesn't
if(nodes[node2] == -1) return -1;
//In below case both nodes are in same subgraph so we
//need to check the length of two alternate paths
if(cnt1 > cnt2)
return node2;
else
return mark;
}

Предположим, у меня есть компонент графа (по сути, подграф), например:

В этом случае, если я хочу найти ближайший узел из 7 & 9 Я получаю ответ 9, пока он должен быть 8. Хотя я понимаю, что это потому, что у меня есть условие cell1! = Cell2 в обоих циклах, но я собираюсь на весь цикл в случае, если я уберу то, что требует больше времени. Также я чувствую, что это решение загромождено множественными if. Можем ли мы найти более простое решение? (возможно, O (LOGN) основан)

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