检查DAG图中的2个节点是否有共同的父节点

Question

输入如下：

一个int[][]，每个子数组包含2个int，即{parent,child}，意味着有一个从parent->child的路径。

例如

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

  1   2   4
   \ /   / \
    3   5   8
     \ / \   \
      6   7   9

[3, 8] => false
[5, 8] => true
[6, 8] => true

我的想法：

• 将输入数据表示为一个DAG图，其中数据存储在像这样的映射中Map ，其中key是顶点，value是它的邻接列表。并且图形中的方向是相反的（与输入数据相比）为子->parent，以便于查找parent.
• 使用函数FindAvailablePartners（整数顶点）查找单个顶点的所有父节点（直接和间接），并返回Set .
• 因此，只需为每个输入顶点调用findavailableparents()一次，然后比较返回的2个集是否有交集。如果是，那么他们有共同的父母；否则，它们不会。

我的问题是：

• 上面解的时间复杂度在O(1)~O(E)之间，对吗？（E是图中的边计数）
• 有更好的解决方案吗？

Answer 1

假设您有多个输入，现在BFS将花费大约O(E)时间来处理每个输入。

所有输入都可以在O(logn)中查询，如果我们做一些预先计算，大约需要O(nlogn)时间

基本上，您希望找到这些节点最不常见的祖先
这篇topcoder中的线程讨论了可以扩展为DAG的树的逻辑
您也可以参考这个问题来获得一些进一步的想法