标识节点位于两个其他节点之间

Question

给定树。边信息以邻接表格式给出。

节点号为1、2、3、.... n

树的根总是1

现在，给出了两个指标。问题是从根(1)到另一个索引的路径上是否存在上述两个索引中的任何一个。

1. 节点数为10^5。
2. 可以触发的最大查询，10^5。
3. 父Id总是小于子Id。

示例:-

边给定:-

1 2
2 5
1 3
3 7
1 4
4 8
8 9

问题——

2 3  ( Answer - Not possible, from 1 to 2, 3 never comes in between and from 1 to 3, 2 never comes in between.)
8 9  ( Answer - Possible, 8 lies in between 1 and 9)

下一个示例:-

1 2
2 4
2 5
1 3
3 6
3 7
3 8

Answer 1

算法如下:-

1. 从根开始，并注意每个节点的IN TIME和OUT TIME。如你所说，邻接表是给定的。这可以通过在Time complexity O(Total number of nodes).中使用DFS来实现。

2. 一个节点"B"是另一个节点"A"的后代，只有在一个条件下。

   IN_TIME (A) & lt;IN_TIME(B) and OUT_TIME(B)

这样，Query将在 0 (1)时间内处理。

Answer 2

假设父节点的ID(更靠近根的那个)总是大于子节点的ID，就像你的例子中所看到的那样，你可以很容易地从任何边看到它是通向根还是远离根。因此，基本算法是:

given nodes n and m
find edge (x, n) or (n, x) such that x < n
repeat with node x until x is m or x is root

我不认为有一种更快的方法来找出一个节点是否在根和另一个之间。当然，您可以通过使用适当的数据结构来提高性能，例如，首先将每个节点映射到散列集中的父节点。下面是Python中的一个示例:

ROOT = 1
edges = ((1, 2), (2, 4), (2, 5), (1, 3), (3, 6), (3, 7), (3, 8))
parents = {}
for edge in edges:
    parent, child = min(edge), max(edge)
    parents[child] = parent
def is_anchestor_of(p, c):
    while c > p:
        if parents[c] == p:
            return True
        c = parents[c]
    return False

创建哈希映射的时间和空间复杂性在节点或边的数量上都是O(n)(这在树中几乎相同)，is_anchestor_of的平均情况复杂性是O(logn)，但在最坏的情况下(极度不平衡的树或链)可能会恶化到O(n)。

您可以通过将每个节点映射到它的所有锚点来提高查找复杂性。创建这个哈希映射的复杂度是O(n log n)时间和空间复杂度，如果我没记错的话，但在最坏的情况下复杂度可能会达到O(n^2)在任何情况下，使用这种结构，is_anchestor_of的复杂度是0(1)，因为它只是在哈希映射中查找，然后在哈希集中查找。

anchestors = {}
for node in parents:
    anchestors[node] = set([ ROOT ])
    p = parents[node]
    while p != ROOT:
        anchestors[node].add(p)
        p = parents[p]
def is_anchestor_of(p, c):
    return p in anchestors[c]

在这两种情况下，只需检查其中一个是否是另一个的锚定。

def on_one_path(x, y):
    return is_anchestor_of(x, y) if x < y else is_anchestor_of(y, x)
print on_one_path(3, 8)

---

更新:似乎有一个更有效的方法;参见@Loha的答案

Answer 3

对于每个节点，构造树中其上方节点的排序列表:

1 {}
2 {1}
3 {1}
4 {1}
5 {1, 2}
7 {1, 3}
8 {1, 4}
9 {1, 4, 8}

然后，当给定一个查询时，在列表中搜索属于另一个(O(logN))的每个节点:

2 3: 2 is not in {1}, and 3 is not in {1}, so the answer is no.
8 9: 9 is not in {1, 4}, but 8 is in {1, 4, 8}, so the answer is yes.

编辑:

正如tobias_k所指出的，还有其他结构，比如哈希表，可以使搜索O(1)。构造表是O(n)，很简单——只是遍历边缘列表并将它们放入。