algorithm - 图算法/不相交集

Question

我正在尝试解决这个问题，但无法快速解决。

简而言之 - 我们有一个图（有向图），我们想找出从哪个节点（给出一组可供选择的节点）我们可以访问最多的节点。一个简单的实现是从每个节点运行 DFS/BFS，看看我们可以访问多少。但是它太慢了，因为图中有超过 5000 个节点。运行 5000 BFS/DFS 需要很长时间。

另一方面我也觉得这个问题可能与不相交集数据结构有关？但是我无法以这种方式制定它，因为在我不相交的集合实现中提到了一些提到的规则。

有人可以提示如何解决这个问题吗？

Answer 1

1. 使用Tarjan 算法(O(V+E))查找强连通分量(SCC) ，并创建 SCC 图。
2. 对生成的 SCC 图进行拓扑排序（它是DAG）。
3. 从最后到第一个，找到每个组件可到达的节点数。
4. 选择一个在 SCC 中可以达到最大节点数的节点。

第 3 步 - 详细说明：

（为了清楚起见，我将原始图中的顶点表示为“节点”，将 SCC 图中的顶点表示为“顶点”）。

在第 3 步中，您希望找到从 SCC 的每个顶点可到达的节点数。这可以通过显式查找此集合或仅查找节点数来完成：

1. 显式查找从每个顶点可到达的节点集：
   这非常简单，每个顶点都有一组关联的节点，您需要通过对 SCC 图前导的所有边进行联合来找到与每个顶点关联的集合从当前顶点。
2. 使用包含/排除来查找可到达的节点数：
   包含/排除是一种用于计算集合中可能存在重复的集合的大小的技术。例如，如果您有 2 个集合，则它们的并集大小为|A|+|B|- |A[intersection]B|.
   对于 3 个集合 A、B、C：（|A|+|B|+|C|-|A[intersrction]B| - |A[intersection]C| - |B[intersection]C + |A[intersection]B[intersection]C|
   依此类推）
   使用包含/排除 - 这些集合是先前的节点，并且交集基于 2 个不同的顶点，这些顶点稍后将自身链接到同一个顶点。