我试图解决this problem问题，但无法快速解决。
简而言之-我们有一个图（有向的），我们想找出我们可以访问最多节点的节点（从中选择一组节点）一个简单的实现是从每个节点运行DFS/BFS并查看我们可以访问多少个节点但是它太慢了，因为图中有超过5000个节点。运行5000个BFS/DFS需要很长时间。
另一方面，我也有一种感觉，这个问题可能与不相交的集合数据结构有关？但我无法像在我的不相交集合中实现上述规则那样来表述它。
有人能提示一下如何解决这个问题吗？
最佳答案
使用Strongly Connected Components查找Tarjan's algorithm（scc）
（o（v+e）），并创建scc图。
Topologically sort生成的scc图（它是aDAG）。
从last到first，查找每个组件可访问的节点数。
选择一个在SCC中可以达到最大节点数的节点。
第3步-阐述：
（为了说明原因，我将原始图中的一个顶点表示为“节点”，而SCC图中的一个顶点表示为“顶点”）。
在步骤3中，您希望找到可以从SCC的每个顶点访问的节点数这可以通过显式查找此集合或仅查找节点数来完成：
显式查找可从每个顶点访问的节点集：
这是非常直接的，每个顶点都有一个关联的节点集，您需要通过对scc图上从当前顶点开始的所有边进行并集来找到与每个顶点关联的集。
使用inclusion/exclusion查找可访问的节点数：
包含/排除是一种用于计算集合的并集大小的技术，集合中可能有重复的集合。例如，如果有两个集合，则它们的并集大小为|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|
（等等）
使用包含/排除-集合是前一个节点，交叉点基于两个不同的顶点，这些顶点稍后将自己链接到同一个顶点。