algorithm - 使用 Q 查询遍历图形中的最后一个节点

Question

给定一个有 N 个节点的有向图(1<=N<=100000)每个节点将只有一个出边，但可以有多个入边。有 Q(1<=Q<=10^5) 个查询，每个查询有 2 种类型。

1. 在第一个查询中，我们必须判断我们是否从节点“A”开始遍历图形，然后是我们停止的最后一个节点。如果我们永不停止，则返回 -1。
2. 第二种类型的查询是我们可以删除节点“A”的出边

我知道我们可以解决每个查询复杂度为 O(N) 的问题(总体复杂度为 QN )，但由于查询数量很高 (10^5)，这似乎不是有效的解决方案？

知道如何以更好的时间复杂度解决这个问题吗？谢谢

Answer 1

如果你不需要在线回答查询，简单的方法是实现带路径压缩的联合查找并向后处理输入。通过链接从不删除的每个弧来初始化(下面的特殊情况)。向后扫描，对于第二种类型的查询，添加圆弧，除非它会创建一个循环，在这种情况下，将尾部链接到 ID 为 -1 的特殊顶点。要回答第一种查询，请使用路径压缩找到根。运行时间将为 O((Q + N) log N)。