c++ - 图论 : Breadth First Search

Question

有n个顶点由m条边相连。有些顶点是特殊的，有些是普通的。至多有一条路径从一个顶点移动到另一个顶点。

第一个查询:我需要找出有多少对直接或间接相连的特殊顶点。

我的方法:我将应用 BFS(通过队列)来查看有多少节点以某种方式相互连接。让我在此发现的特殊顶点的数量为 n，那么我的查询的答案将是 nC2。我将重复此操作直到所有顶点被访问。

第二个查询:任意两个特殊顶点之间的路径上有多少个顶点。

我的方法:在查询 1 的方法中，我将应用 BFS 找出任意两个特殊顶点之间的路径，然后回溯并标记路径上的顶点。

问题:顶点数可以高达 50,000。因此，应用 BFS，然后我猜，对于我的时间限制(2 秒)，回溯会更慢。

我有所有顶点的列表和它们的邻接列表。现在，在 BFS 时将顶点推送到我的队列中时，我还能以某种方式计算查询 2 的答案吗？有没有更好的方法可以用来解决问题？输入格式将是这样的，我将被一一告知一个顶点是否特殊，然后我将获得有关连接两个顶点的第 i 条路径的信息。从一个顶点移动到另一个顶点最多有一条路径.

Answer 1

第一个查询通过将森林分割成树来解决。

从完整的顶点集开始，选择一个，然后从那里访问您可以访问的每个节点，直到您不能访问更多的顶点。这是一棵树。对每棵树重复。

你现在有 K 个顶点包，每个包含 0-j 个特殊顶点。这就回答了第一个问题。

对于第二个问题，我想一个简单的解决方案确实是 BFS 为子图中的每一对顶点到另一个顶点之间的路径。

您还可以利用子图的树性质。本题:How to find the shortest simple path in a Tree in a linear time?提到它。 (虽然我还没有真正深入研究过)