C++のグラフのエッジの一部ではないノードの数を最大化する

これを行うには、ノードの数がnで、n（n-1）/2個のエッジがある完全グラフを作成します。

edge =n（n-1）/ 2（ここではノードの場合はn）

2 * edge =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つのノードが必要です。この場合、両方が占有されています。ノードが残っていません。

以下のプログラムで使用されているアプローチは次のとおりです

• 利用可能なデータのために2つの可変ノードとエッジを取ります。

• 関数maximum（intノード、intエッジ）は必要ありません。ノードとエッジの数をパラメータとして返し、グラフ内のエッジの一部ではない最大ノードの数を返します

• 変数i、temp、maxを取ります。

• i=0からi<=nodes

  までのループFORを開始します

• temp =i *（i-1）

  を計算します

• 変数の合計を2*エッジとして計算します

• 温度が合計より高くなるときはいつでも、FORを破ってください

• maxをmax=nodes-i

  として計算します

• 結果を最大値として返します。

例

#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