Số cạnh tối đa trong đồ thị hai phía trong C++

Đề bài

Cho số nguyên N đại diện cho số đỉnh. Nhiệm vụ: tìm số cạnh tối đa có thể có trong đồ thị hai phía (Bipartite graph) có N đỉnh.

Đồ thị hai phía (Bipartite Graph)

• Là đồ thị có 2 tập đỉnh
• Các đỉnh trong cùng một tập không bao giờ chia sẻ cạnh với nhau

Ví dụ

Nếu N = 10 thì có tổng 25 cạnh:

• Cả hai tập đều chứa 5 đỉnh và mỗi đỉnh của tập đầu nối với mọi đỉnh của tập hai
• Tổng cạnh = 5 × 5 = 25

Thuật toán

• Số cạnh tối đa khi mọi đỉnh của một tập nối với mọi đỉnh của tập kia: cạnh = m × n (m, n là kích thước 2 tập)
• Để tối đa hóa số cạnh, m phải bằng hoặc gần bằng n nhất có thể
• Công thức tính số cạnh tối đa: (n × n) / 4 (làm tròn xuống)

Chương trình C++

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

int getMaxEdges(int n) {
    return floor((n * n) / 4);
}

int main() {
    int n = 7;
    cout << "Maximum edges = " << getMaxEdges(n) << endl;
    return 0;
}

Kết quả

Maximum edges = 12

Giải thích

Với n = 7: chia thành 2 tập có 3 và 4 đỉnh → 3 × 4 = 12 cạnh. Công thức floor(n²/4) cho kết quả chính xác cho mọi n.