图论:广度优先搜索

Question

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

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

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

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

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

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

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

Answer 1

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

从一组完整的顶点开始，拾取一个顶点，然后从那里访问每个节点，直到不能再访问任何顶点。这是一棵树。对每棵树重复上述步骤。

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

对于第二个问题，我认为一个微不足道的解决方案确实是BFS，即子图中每对顶点到另一个顶点之间的路径。

你也可以利用你的子图的树形特性。问题：How to find the shortest simple path in a Tree in a linear time?提到了这一点。(不过，我还没有真正深入研究过这个问题)

Answer 2

假设arr是布尔数组，如果arri是特殊的，则arri为1，否则为0。find-set(i)返回树的根节点。因此，位于同一树中的任何节点都会返回相同的数字。

for(int i=1; i<n; i++){ 
      for(int j=i+1; j<=n; j++){
            if(arr[i]==1 && arr[j]==1){        //If both are special
                if(find-set(i)==find-set(j)){  //and both i and j belong to the same tree
                    //k++ where k is answer to the first query.
                    //bfs(i,j) and find the intermediate vertices and do ver[i]=1 for the corresponding intermediate vertex/node.
                }
            }
      }        
}

最后，在ver矩阵中计算1的个数，这是对第二个查询的答案。