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

Narendra Kumar

更新于: 2020年1月10日

293 次查看

开启你的 职业生涯

完成课程获得认证

开始学习