Tối đa hóa số nút không thuộc cạnh nào trong đồ thị C++

Cho một đồ thị với số nút (nodes) và số cạnh (edges). Mục tiêu là tìm số lượng nút tối đa có thể không thuộc cạnh nào (nút cô lập) trong một đồ thị có thể có tối đa số cạnh cho trước.

Phân tích bài toán

Để tối đa hóa số nút cô lập, ta nên tập trung tất cả các cạnh vào một tập con nhỏ nhất có thể của các nút, tạo thành một đồ thị hoàn chỉnh (complete graph).

Đồ thị hoàn chỉnh với k nút có số cạnh tối đa: k(k-1)/2.

Cho số cạnh E cho trước, ta cần tìm k nhỏ nhất sao cho k(k-1)/2 ≥ E.

Số nút cô lập tối đa = N - k (với N là tổng số nút).

Ví dụ minh họa

Ví dụ 1:

• Input: nodes = 5, edges = 2
• Output: 2
• Giải thích: 2 cạnh cần tối thiểu 3 nút (tạo thành đường đi) hoặc 4 nút (2 cạnh rời rạc). Với 3 nút thì còn 2 nút cô lập.

Ví dụ 2:

• Input: nodes = 2, edges = 1
• Output: 0
• Giải thích: Cần ít nhất 2 nút để tạo 1 cạnh, không còn nút nào cô lập.

Mã nguồn C++

#include <bits/stdc++.h>
using namespace std;

int maximum(int nodes, int edges) {
    int i, temp = 0, max_isolated;
    for (i = 0; i <= nodes; i++) {
        temp = i * (i - 1);
        int total = 2 * edges;
        if (temp >= total) {
            break;
        }
    }
    max_isolated = nodes - i;
    return max_isolated;
}

int main() {
    int nodes = 10;
    int edges = 5;
    cout << "So nut co lap toi da: " << maximum(nodes, edges) << endl;
    return 0;
}

Kết quả chạy chương trình

So nut co lap toi da: 6

Giải thích kết quả (nodes=10, edges=5)

• Tìm k nhỏ nhất: k(k-1)/2 ≥ 5
• k=4: 4×3/2 = 6 ≥ 5 ✓
• Số nút cô lập = 10 - 4 = 6

Độ phức tạp

• Thời gian: O(N) - vòng lặp tối đa N lần.
• Không gian: O(1).

Cải tiến O(1)

Giải phương trình bậc 2: k² - k - 2E ≥ 0 → k = ceil((1 + √(1+8E))/2)

int maximum_optimized(int nodes, int edges) {
    if (edges == 0) return nodes;
    int k = ceil((1 + sqrt(1 + 8.0 * edges)) / 2);
    return max(0, nodes - k);
}