给定一个有n个节点的有向图（1每个节点只有一个传出边，但可以有多个传入边。有Q（1<=Q<=10^5）查询，其中每个查询有两种类型。
在第一个查询中，我们必须判断是否开始从节点“a”遍历图形，然后判断哪一个节点是我们停止的最后一个节点。如果我们不停，那就返回-1。
第二种类型的查询是，我们可以删除节点“A”的传出边
我知道我们可以解决每个查询复杂度（QN复杂度）的问题，但是由于查询的NO是高的（10 ^ 5），这似乎不是有效的解决方案。
你知道如何用更好的时间复杂度来解决这个问题吗？
谢谢
最佳答案
如果您不需要在线回答查询，那么简单的方法是实现带路径压缩的联合查找并向后处理输入。通过链接从未删除的每个弧（使用下面的特殊情况）进行初始化。向后扫描，对于第二种类型的查询，添加弧，除非它会创建一个循环，在这种情况下，将尾部链接到id为-1的特殊顶点要回答第一种查询，请使用路径压缩查找根。运行时间为O（（Q+N）logn）。
关于algorithm - 使用Q查询遍历图形中的最后一个节点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/54054206/