C++ 中二分圖的最大邊數

問題陳述

給定一個整數 N，表示頂點的數量。任務是找到 N 個頂點的二分圖中可能的最大邊數。

二分圖

  • 二分圖是指具有兩組頂點的圖。
  • 這些集合使得同一集合中的頂點之間永遠不會共享邊。

示例

如果 N = 10，則將共有 25 條邊 -

  • 兩個集合都包含 5 個頂點，並且第一個集合的每個頂點都與第二個集合的每個其他頂點有一條邊。
  • 因此，總邊數為 5 * 5 = 25

演算法

  • 當給定集合的每個頂點都與另一個集合的每個其他頂點有一條邊時，邊數將最大化，即邊 = m * n，其中 m 和 n 是兩個集合中的邊數。
  • 為了最大化邊數，m 必須等於或儘可能接近 n。
  • 因此，最大邊數可以用以下公式計算 -

            (n * n) / 4

示例

 現場演示

#include <bits/stdc++.h>
using namespace std;
int getMaxEdges(int n) {
   return floor((n * n) / 4);
}
int main() {
   int n = 7;
   cout << "Maximum edges = " << getMaxEdges(n) << endl;
   return 0;
}

輸出

編譯並執行上述程式時，會生成以下輸出 -

Maximum edges = 12

更新於: 2020年1月10日

293 次檢視

開啟你的 職業生涯

完成課程獲得認證

開始學習
廣告