หาจำนวนโหนดสูงสุดที่ไม่ได้เชื่อมต่อกับขอบใดๆ ในกราฟ ใน C++

ได้รับกราฟที่มีโหนดและขอบ ต้องการหาจำนวนโหนดสูงสุดที่ไม่ได้เป็นส่วนหนึ่งของขอบใดๆ เรารู้ว่าในกราฟสมบูรณ์ (complete graph) จำนวนขอบสูงสุดคือ n(n-1)/2 โดยที่ n คือจำนวนโหนด

แนวคิด

หาจำนวนโหนดน้อยที่สุดที่จำเป็นสร้างขอบที่กำหนด โหนดที่เหลือจะเป็นโหนดที่ไม่ได้เชื่อมต่อ

• ขอบ = n(n-1)/2 → 2×ขอบ = n(n-1)
• วนหา n น้อยที่สุดที่ทำให้ n(n-1) ≥ 2×ขอบ
• โหนดที่ไม่ได้เชื่อมต่อ = โหนดทั้งหมด - n

ตัวอย่าง

อินพุต: nodes = 5, edges = 2

เอาต์พุต: 2

คำอธิบาย: 2 ขอบต้องการโหนดขั้นต่ำ 3 โหนด (สูงสุด 4) โหนดเหลือ 5-3 = 2

อินพุต: nodes = 2, edges = 1

เอาต์พุต: 0 (ทั้ง 2 โหนดถูกใช้สร้างขอบ)

ตัวอย่างโค้ด C++

#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;
    return 0;
}

ผลลัพธ์

Maximize number of nodes which are not part of any edge in a Graph are: 6