数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++中最大化图中不属于任何边的节点数
给定一个包含节点和边的图，目标是找到可能连接到图的任何边的最大节点数。我们知道，节点数始终小于或等于完全图中的边数。
我们将通过尝试创建一个完全图来实现这一点，如果节点数为n，则将有n(n-1)/2条边。
边数 = n(n-1)/2 (其中n为节点数)
2 * 边数 = n(n-1)。一旦n(n-1) > 边数，我们就有了额外的节点。所以从i=1迭代到i=n。
直到i(i-1) > 2 * 边数。返回n-i作为结果。
让我们通过例子来理解：
**输入** - 节点数=5，边数=2
**输出** - 图中不属于任何边的最大节点数为：2
**解释** -
2条边至少可以有3个节点，最多可以有4个节点。
对于3个节点，没有边的最大剩余节点数=2
**输入** - 节点数=2，边数=1
**输出** - 图中不属于任何边的最大节点数为：0
**解释** -
至少需要2个节点才能构成一条边。在这种情况下，两个节点都被占用。没有剩余节点。
下面程序中使用的算法如下：
我们使用两个变量nodes和edges来存储可用数据。
函数maximum(int nodes, int edges) 将节点数和边数作为参数，并返回图中不属于任何边的最大节点数。
使用变量i，temp和max。
从i=0开始循环，直到i<=nodes
计算temp = i*(i-1)
计算变量total为2*edges
当temp大于total时，中断循环
计算max为max = nodes - i
返回结果max。
示例
#include <bits/stdc++.h>
using namespace std;
int maximum(int nodes, int edges){
int i, temp = 0, max;
for (i = 0; i <= nodes; i++){
temp = i * (i - 1);
int total = 2* edges;
if (temp >= total){
break;
}
}
max = nodes - i;
return max;
}
int main(){
int nodes = 10;
int edges = 5;
cout<<"Maximize number of nodes which are not part of any edge in a Graph are:"<<maximum(nodes, edges) << endl;
}输出
如果运行以上代码，将生成以下输出：
Maximize number of nodes which are not part of any edge in a Graph are: 6
更新于：2020年8月31日
69 次浏览
广告