Số cạnh tối đa được thêm vào cây để nó vẫn là biểu đồ Bipartite trong C ++

Tuyên bố vấn đề

Một cây luôn là một Đồ thị lưỡng cực vì chúng ta luôn có thể chia thành hai tập rời rạc với các mức thay thế.

Nói cách khác, chúng tôi luôn tô màu nó bằng hai màu sao cho các mức xen kẽ có cùng màu. Nhiệm vụ là tính toán số tối đa. các cạnh có thể được thêm vào cây để nó vẫn là Biểu đồ lưỡng cực.

Ví dụ

Các cạnh của cây được biểu diễn theo các cặp đỉnh như sau -

{1, 2}

{1, 3}

{2, 4}

{3, 5} thì chúng ta cần thêm 2 cạnh nữa để giữ nó là Đồ thị lưỡng cực

• Trong biểu đồ tô màu, biểu đồ {1, 4, 5} và {2, 3} từ hai tập hợp khác nhau. Vì, 1 được kết nối với cả 2 và 3
• Chúng ta còn lại các cạnh 4 và 5. Vì 4 được kết nối thay thế với 2 và 5 với 3. Chỉ còn lại tùy chọn là {4, 3} và {5, 2}

Thuật toán

• Thực hiện một phép duyệt DFS hoặc BFS đơn giản của đồ thị và tô màu nó bằng hai màu
• Trong khi tô màu cũng theo dõi số lượng các nút được tô bằng hai màu. Đặt hai số đếm là count_color0 và count_color1
• Giờ đây, chúng tôi biết các cạnh tối đa mà biểu đồ hai bên có thể có là count_color0 x count_color1
• Chúng ta cũng biết cây có n nút có n-1 cạnh
• Vì vậy, câu trả lời của chúng tôi là count_color0 x count_color1 - (n-1)

Ví dụ

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

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Maximum edges = 2