我被给定了一个有向图，并且给定了其中的两个节点，我需要找到可以从这两个节点到达的最近节点。唯一的问题是我能够使用两个深度优先搜索来完成，但是我被告知要在O(logn)时间内完成。另一个限制是每个单元格 最多只能有一个 出边。输入以大小为N的数组形式给出，其中数组中的每个条目表示该节点所指向的节点的索引。所以这是我尝试过的代码（不完全是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)）正如上图所示，这个图也可能有循环。因此，转换成树不可能吧。