用特定的条件构建图的 C++ 程序

假设我们有两个数字 N 和 K。假设有一个 N 个元素的无向图。N 个顶点满足以下条件 −

• 图是简单且相连的

• 顶点编号从 1 到 N

• 令 M 为图中的边数。边编号从 1 到 M。边的长度为 1。并且边 i 连接顶点 U[i] 到顶点 V[i]。

• 有恰好 K 对顶点 (i, j)，其中 i < j，它们之间的最短距离为 2。

如果这样的图存在，我们必须构建该图。否则返回 -1。

因此，如果输入类似于 N = 5; K = 3，则输出将是

步骤

为了解决这个问题，我们将按照以下步骤进行 −

if k > (n - 1) * (n - 2) / 2, then:
   print -1
print ((n - 1) * (n - 2) / 2 - k + n - 1)
for initialize i := 1, when i < n, update (increase i by 1), do:
   print pair (1, i + 1)
count := (n - 1) * (n - 2) / 2 - k
for initialize i := 2, when i <= n, update (increase i by 1), do:
   for initialize j := i + 1, when j <= n, update (increase j by 1), do:
      if count <= 0, then:
         return
      print pair (i, j)
      (decrease count by 1)

示例

让我们看看以下实现来获得更好的理解 −

#include <bits/stdc++.h>
using namespace std;

void solve(int n, int k){
   if (k > (n - 1) * (n - 2) / 2){
      cout << -1 << endl;
   }
   cout << (n - 1) * (n - 2) / 2 - k + n - 1 << '\n';
   for (int i = 1; i < n; i++){
      cout << 1 << ", " << i + 1 << '\n';
   }
   int count = (n - 1) * (n - 2) / 2 - k;
   for (int i = 2; i <= n; i++){
      for (int j = i + 1; j <= n; j++){
         if (count <= 0){
            return;
         }
         cout << i << ", " << j << '\n';
         count--;
      }
   }
}
int main(){
   int N = 5;
   int K = 3;
   solve(N, K);
}

输入

5, 3

输出

7
1, 2
1, 3
1, 4
1, 5
2, 3
2, 4
2, 5

阿纳布·查克拉博蒂

更新于： 2022-03-03

482 次浏览

启动你的 职业

完成课程认证

开始