2

我的任务是有效地处理带有节点Q的生成树图中的查询。N

每个查询都引用我需要处理的一条边，并且我应该输出图中删除该边后剩余的两个组件中的每一个的大小。

我目前的想法是从由该边缘连接的两个节点启动一个 DFS，确保 DFS 永远不会遍历边缘本身。这样，我将能够及时找到两个组件的大小，O(N)总复杂度为O(Q * N).

但是，我认为我可以做一些预处理来进一步降低我的解决方案的时间复杂度，但我就是想不出那可能是什么。有人可以指出我正确的方向吗？

4

1 回答 1

1

好吧，这是我刚刚提出的一个策略：

首先，找到具有精确度的任何节点1（保证存在于生成树图中；它被称为“叶”）。从该节点运行 DFS，保留一个count表示到目前为止已访问的节点数的变量。每次遍历一条边时，通过删除该边形成的两个组件的大小必须相等count，并且N - count由于树的特殊属性（具体来说，任何一对节点之间只有一条路径）。这导致算法具有O(N)预处理和O(1)查询回答，总时间复杂度为O(N + Q).

于 2020-09-12T17:08:02.927 回答