nearest meeting node of two given nodes in a Directed Graph
<p>I am given a Directed Graph and given two nodes in it I need to find the nearest node  that can be reached from both of them. The only problem is I am able to do it with two dfs but I was told to do it in O(logn). Additional constraint is that each cell can have <strong>at most one</strong> outgoing edge. Input is given as an array of size N where eachentry in array denotes the index of node this node is leading to. So for this is the code I have tried(not exactly dfs but still):  </p>

<pre><code>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 &lt; N; i++){
    visited[i] = 0;
  }

  while((nodes[node1] != node1) &amp;&amp; (nodes[node1] != -1) &amp;&amp; (visited[node1] == 0) &amp;&amp; (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) &amp;&amp; (nodes[node2] != -1) &amp;&amp; (visited[node2] != 2) &amp;&amp; (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 &lt;&lt; visited[node1] &lt;&lt; visited[node2] &lt;&lt; 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) &amp;&amp; (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 &gt; cnt2)
    return node2;
  else
    return mark;
}  
</code></pre>

<p>Suppose I have a component of a graph(essentially a subgraph) like following:<br>
<a href="https://i.stack.imgur.com/ajGZI.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ajGZI.png" alt="enter image description here"></a></p>

<p>In this case if I want to find the nearest node from 7 &amp; 9 I am getting the answer 9 while it should be 8. Though I understand it is because I have condition cell1 != cell2 in both loops but I am going for entire cycle in case I remove that which invites more time. Also I feel this solution as cluttered with multiple if's. Can we have a simpler solution? (possibly <strong>O(logn)</strong> based)</p>

<p>This graph can also have cycles as illustrated by image above. So converting to tree is not possible I guess.</p>