偶数距离节点对的数量（使用 BFS）

---

在本文中，我们将找到图中彼此之间距离为偶数的节点对的数量。我们将使用广度优先搜索 (BFS) 方法来查找总数。

在本文讨论的方法中，我们将使用一个包含整数对的队列数据结构。队列数据结构将允许我们使用广度优先搜索算法 (BFS) 遍历图。我们将选择一个随机节点并从该节点应用广度优先搜索。我们将使用两个变量来跟踪出现在我们给定节点的偶数级别的节点数量，以及出现在我们给定节点的奇数级别的节点数量。所有与源节点距离为偶数的节点也彼此之间距离为偶数，所有与源节点距离为奇数的节点也彼此之间距离为偶数。因此，使用这两个变量，我们可以计算彼此之间距离为偶数的节点总数。

问题陈述 - 给定一个图，该图是连通的并且不包含循环，包含 N 个节点和 N-1 条边，我们需要找到彼此之间距离为偶数的节点对的总数。

注意 - 图以邻接表的形式给出。

示例

输入

            0
           /
         1
       /
     2
   /
 3

输出

2

解释

以下是唯一彼此之间距离为偶数的节点 {0,2}、{1,3}，所以输出为 2

输入

    0
   /  \
  1    2
      / \
     3   4

输出

4

解释

彼此之间距离为偶数的节点为 -

{0,3}, {0,4}, {1,2}, {3,4}

因此，输出为 4。

输入

      0
     /  \
    1     2
   / \    / \
  3   4   5  6

输出

11

解释

彼此之间距离为偶数的节点为 -

{0,3}, {0,4}, {0,5}, {0,6}, {1,2}, {3,4}, {3,5}, {3,6}, {4,5}, {4,6}, {5,6}

所以，输出为 11。

方法

在这种方法中，我们将使用一个包含整数对的队列数据结构。我们将随机选择一个源节点并将其推入队列。然后，我们将使用选定的源节点应用广度优先搜索算法。我们将维护两个变量，它们将跟踪与我们的源节点距离为偶数的节点数量以及与我们的源节点距离为奇数的节点数量。某个节点的极性将存储在对中的第二个整数中。使用这两个变量，我们可以计算彼此之间距离为偶数的节点总数。

算法

• 步骤 1 - 创建一个向量 vis，它将跟踪我们已访问的节点。

• 步骤 2 - 创建一个队列数据结构。

• 步骤 2.1 - 队列将包含一对整数，对中的第一个整数将是图中的节点，第二个整数将表示极性，即节点与我们的源节点的距离是偶数还是奇数。

• 步骤 2.2 - 将源节点与极性 0 推入队列。

• 步骤 2.3 - 创建两个变量，它们将存储奇数和偶数级别的节点数量。

• 步骤 3 - 循环直到队列变空

• 步骤 3.1 - 在每次迭代中，取出队列的第一个元素并将其标记为已访问。

• 步骤 3.2 - 循环当前节点的每个邻居

• 步骤 3.3 - 如果邻居未被访问，则将其添加到队列中，其极性与当前节点的极性相反。

• 步骤 3.4 - 如果当前节点的极性为偶数，则将 1 加到偶数变量中，否则将 1 加到奇数变量中

• 步骤 4 - 队列变空后，答案可以计算如下：答案 = 偶数*(偶数-1)/2 + 奇数*(奇数-1)/2

• 步骤 5 - 返回答案。

示例

下面的 C++ 程序是上述方法的实现 -

#include <bits/stdc++.h>
using namespace std;
int Count_pair_nodes(vector<vector<int>> &gph){
   int N = gph.size();
   vector<int> vis(N,0);
   queue<pair<int,int>> que;
   que.push({0,0});
   long long even_pos = 0 , odd_pos = 0;
   while(!que.empty()){
      int vertex = que.front().first , odd_even = que.front().second;
      que.pop();
      vis[vertex] = 1;
      for(auto it:gph[vertex]){
         if(vis[it]==0)que.push({it,1-odd_even});
      }
      if(odd_even)even_pos++;
      else odd_pos++;
   }
   long long ans = even_pos*(even_pos-1)/2 + odd_pos*(odd_pos-1)/2;
   return ans;
}
int main(){
   vector<vector<int>> gph = {
      {1},
      {0,2},
      {1,3},
      {2}
   };
   cout<<Count_pair_nodes(gph)<<endl;
   return 0;
}

输出

2

时间复杂度 - O(N)，其中 N 是图中节点的数量。

空间复杂度 - O(N)