資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中將最大數量的邊新增到樹中以使其保持二分圖
問題陳述
樹總是二分圖，因為我們總是可以將其分解成兩個不相交的集合，並交替設定級別。
換句話說，我們總是用兩種顏色對其進行著色，這樣交替的級別具有相同的顏色。任務是計算可以新增到樹中的最大邊數，以使其保持二分圖。
示例
樹邊以頂點對的形式表示如下：
{1, 2}
{1, 3}
{2, 4}
{3, 5} 然後我們需要 2 條額外的邊來保持它為二分圖
- 在著色圖中，圖 {1, 4, 5} 和 {2, 3} 來自兩個不同的集合。因為 1 與 2 和 3 都相連
- 我們剩下邊 4 和 5。因為 4 已經連線到 2，而 5 連線到 3。唯一剩下的選項是 {4, 3} 和 {5, 2}
演算法
- 對圖進行簡單的 DFS 或 BFS 遍歷並用兩種顏色對其進行著色
- 在著色的同時，還要跟蹤用兩種顏色著色的節點的數量。假設這兩個計數為 count_color0 和 count_color1
- 現在我們知道二分圖可以具有的最大邊數是 count_color0 x count_color1
- 我們也知道具有 n 個節點的樹具有 n-1 條邊
- 所以我們的答案是 count_color0 x count_color1 – (n-1)
示例
#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;
}輸出
編譯並執行上述程式時，它會生成以下輸出：
Maximum edges = 2
更新於：2020年1月10日
273 次檢視
廣告