C ++中Bipartite图的最大边数
问题陈述
给定一个整数N，它表示顶点的数量。任务是在N个顶点的二部图中找到最大可能的边数。
二部图
二分图是一个具有2组顶点的图。
该集合使得同一集合中的顶点之间永不共享边。
示例
如果N=10，则总共有25条边-
两个集合都将包含5个顶点，并且第一集合的每个顶点都将具有第二集合的每个其他顶点的边
因此，总边将为5*5=25
算法
当给定集合的每个顶点都具有另一集合的每个其他顶点的边缘时，边缘的数量将最大，即edges=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
热门推荐
10 预祝高尔夫的祝福语简短
11 迟到的过年祝福语简短
12 阳历新年祝福语大全 简短
13 鼠年新年贺卡祝福语简短
14 古风婚礼祝福语唯美简短
15 对同事简短生日祝福语
16 薛之谦祝福语简短
17 新婚祝福语简短十六字
18 生日祝福语古朴简短独特