เพิ่มจำนวนโหนดสูงสุดซึ่งไม่ได้เป็นส่วนหนึ่งของขอบใดๆ ในกราฟใน C++

เราได้รับกราฟที่มีโหนดและขอบ เป้าหมายคือการหาจำนวนโหนดที่เป็นไปได้สูงสุดที่เชื่อมต่อกับขอบใดๆ ของกราฟ เรารู้ว่าไม่มี ของโหนดจะน้อยกว่าหรือเท่ากับจำนวนขอบในกราฟที่สมบูรณ์เสมอ

เราจะทำสิ่งนี้โดยพยายามสร้างกราฟที่สมบูรณ์โดยที่จำนวนโหนดเป็น n แล้วจะมี n(n-1)/2 ขอบ

edge=n(n-1)/2 (ที่นี่ n สำหรับโหนด )

2*ขอบ=n(n-1). เมื่อ n(n-1)> ไม่ ของขอบแล้วเรามีโหนดพิเศษ ดังนั้นวนซ้ำจาก i=1 ถึง i=n

จนถึง i(i-1)>2*edge. คืนค่า n-i เป็นผลลัพธ์

ให้เราเข้าใจด้วยตัวอย่าง -

ป้อนข้อมูล − โหนด=5, ขอบ=2

ผลผลิต − เพิ่มจำนวนโหนดที่ไม่เป็นส่วนหนึ่งของขอบใดๆ ในกราฟให้สูงสุด − 2

คำอธิบาย −

2 ขอบสามารถมีอย่างน้อย 3 โหนดและสูงสุด 4 โหนด

สำหรับ 3 โหนด โหนดด้านซ้ายสูงสุดไม่มีขอบ =2

ป้อนข้อมูล − โหนด=2, ขอบ=1

ผลผลิต − จำนวนโหนดสูงสุดที่ไม่ได้เป็นส่วนหนึ่งของขอบใดๆ ในกราฟคือ − 0

คำอธิบาย −

ต้องมีอย่างน้อย 2 โหนดเพื่อสร้างขอบ ในกรณีนี้ทั้งคู่ถูกครอบครอง ไม่มีโหนดเหลือ

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

• เราใช้โหนดตัวแปรสองโหนดและขอบสำหรับข้อมูลที่มี

• ฟังก์ชั่นสูงสุด (โหนด int, ขอบ int) รับหมายเลข ของโหนดและขอบเป็นพารามิเตอร์ และส่งคืนจำนวนโหนดสูงสุดที่ไม่เป็นส่วนหนึ่งของขอบใดๆ ในกราฟ

• หาตัวแปร i, temp และ max.

• เริ่มลูป FOR จาก i=0 ถึง i<=nodes

• คำนวณ temp=i*(i-1)

• คำนวณผลรวมของตัวแปรเป็น 2*edge

• เมื่อใดก็ตามที่อุณหภูมิมากกว่ายอดรวม ให้ทำลาย FOR

• คำนวณสูงสุดเป็น 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