algorithm - 在图中找到一组顶点，使每个顶点都能到达 k 个其他顶点

Question

令 G=(V,E) 为有向图，k 为整数。我需要在线性时间内找到顶点组，以便该组中的每个顶点都能恰好到达 k 个顶点(包括它自己)。

我首先想到的是使用 Kosaraju 的算法来找到图中的强连通分量。连通分量内的每个顶点至少可以到达该连通分量中的顶点，所以剩下的就是看组件是如何连接的。但是，我没有想出线性解决方案。

有什么提示吗？

谢谢。

Answer 1

你的第一步是正确的。每个强连通分量都可以用一个顶点代替，其中起始# of reachable vertices 是该分量中的元素数。代入操作后得到有向无环图。现在，对于每个 super 顶点，我们想要找出从它可以到达多少个顶点。一个想法是拓扑排序这个图。完成此操作后，所有箭头都指向一个方向。不失一般性，我们可以假设它们指向右边，所以我们的图表看起来或多或少像这样:

a -> b ----> e -> f -> g
  \             /
    -> c -> d -

对于每个顶点，我们都有它的起始计数器，这是我们从一个强连接组件组装顶点的第一阶段获得的。我们现在想做的是从右到左，每个顶点都有一组可以从它到达的顶点。我们需要的操作是快速合并这个集合。 Find-Union 数据结构提供了帮助。您可以在通常的size 基础上再增加一个字段和 rank它将存储可达顶点的数量并在您进行更新时 union两套。

这将导致几乎线性的时间:O(n * alpha(n))其中 alpha(n)是非常非常小的阿克曼函数的反函数。对于大数据，它不会大于 5 ，因此您可以将其视为常数。

我想知道是否有人可以在没有 alpha 的情况下做到这一点.