title: nearest meeting node of two given nodes in a Directed Graph
body: <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>