c++ - nearest meeting node of two given nodes in a Directed Graph -

i given directed graph , given 2 nodes in need find nearest node can reached both of them. problem able 2 dfs told in o(logn). additional constraint each cell can have at one outgoing edge. input given array of size n eachentry in array denotes index of node node leading to. code have tried(not dfs still):

int leastcommondescendent(int nodes[], int n, int node1, int node2) {   int *visited = new int [n];   int cnt1 = 0; //used counting length of path node1 node2   int cnt2 = 0; //used counting length of path node2 node1   int mark = node1; //storing marker needed later detecting end of search    if(node1 == node2) return node2;   for(int = 0; < 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 first node in cycle has count 2                     //if find node in 2nd iteration has count 2                     //such when node1 == node2 means in same subgraph                     //elsif node1 != node2 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 nodes in different disjoint subgraphs   //and both subgraphs have loops node1 can never equal node2   //cout << visited[node1] << visited[node2] << endl;   if(node1 != node2) return -1;     //in below case both nodes in different disjoint subgraphs     //but there no loop in 1st one(containing node1)     //and 2nd 1 has loop   if ((nodes[node1] == -1) && (visited[node2] == 1)) return -1;     //in below case both nodes in different disjoint subgraphs     //but 1st 1 has loop , second 1 doesn't   if(nodes[node2] == -1) return -1;     //in below case both nodes in same subgraph     //need check length of 2 alternate paths   if(cnt1 > cnt2)     return node2;   else     return mark; }   

suppose have component of graph(essentially subgraph) following:

in case if want find nearest node 7 & 9 getting answer 9 while should 8. though understand because have condition cell1 != cell2 in both loops going entire cycle in case remove invites more time. feel solution cluttered multiple if's. can have simpler solution? (possibly o(logn) based)

this graph can have cycles illustrated image above. converting tree not possible guess.

this reduced (and from) lowest common ancestor in tree (or in forest exact), reversing links of graph.

generally, can done in o(h), stepping "up" tree step step (stepping forward in original graph), , storing found nodes in set until set intersecton not empty.

if pre-processing allowed, 1 can pre-process in linear time better resilts.