Số cạnh tối đa thêm vào cây để vẫn là đồ thị hai phía trong C++

Đề bài

Một cây luôn là đồ thị hai phía (Bipartite Graph) vì có thể chia thành hai tập rời rạc với các cấp bậc xen kẽ. Nói cách khác, luôn có thể tô màu với hai màu sao cho các cấp bậc xen kẽ có cùng màu. Nhiệm vụ: tính số cạnh tối đa có thể thêm vào cây để nó vẫn là đồ thị hai phía.

Ví dụ

Các cạnh của cây được biểu diễn dưới dạng cặp đỉnh:

{1, 2}
{1, 3}
{2, 4}
{3, 5}

Cần thêm 2 cạnh để giữ tính hai phía.

• Tô màu đồ thị: tập {1, 4, 5} và {2, 3} là hai tập khác nhau. Vì 1 nối với cả 2 và 3
• Còn lại cạnh 4 và 5. Vì 4 đã nối với 2 và 5 nối với 3. Chỉ còn tùy chọn {4, 3} và {5, 2}

Thuật toán

1. Duyệt DFS hoặc BFS đơn giản để tô màu đồ thị với hai màu
2. Khi tô màu, đếm số nút mỗi màu: count_color0 và count_color1
3. Số cạnh tối đa của đồ thị hai phía là: count_color0 × count_color1
4. Cây n nút có n-1 cạnh
5. Kết quả: count_color0 × count_color1 - (n - 1)

Chương trình C++

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

long long count_color[2];

void dfs(vector<int> graph[], int node, int parent, int color) {
    ++count_color[color];
    for (int i = 0; i < graph[node].size(); ++i) {
        if (graph[node][i] != parent) {
            dfs(graph, graph[node][i], node, !color);
        }
    }
}

int getMaxEdges(vector<int> graph[], int n) {
    dfs(graph, 1, 0, 0);
    return count_color[0] * count_color[1] - (n - 1);
}

int main() {
    int n = 5;
    vector<int> graph[n + 1];
    graph[1].push_back(2);
    graph[1].push_back(3);
    graph[2].push_back(4);
    graph[3].push_back(5);
    cout << "Maximum edges = " << getMaxEdges(graph, n) << endl;
    return 0;
}

Kết quả

Maximum edges = 2