資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時裝研究
法律研究從樹中移除最大邊數以形成 C++ 中的偶數森林
問題陳述
給定一個具有偶數個頂點的無向樹，我們需要從該樹中移除最大數量的邊，以使所得森林的每個連通分量都具有偶數個頂點。
舉例
在上面所示的樹中，我們可以最多移除以紅色顯示的 2 條邊 0-2 和 0-4，以使每個連通分量都具有偶數個頂點。
演算法
- 從任何起始節點進行 DFS，因為樹是連線的
- 將當前節點下子樹中節點的數量初始化為 0
- 對當前節點的每個子樹遞迴執行以下操作 −
- 如果當前子樹的大小為偶數，則將結果加 1，因為我們可以斷開子樹
- 否則將當前子樹中節點的數量新增到當前計數
舉例
現在，讓我們看一個示例 −
#include <bits/stdc++.h>
using namespace std;
int dfs(vector<int> g[], int u, bool visit[], int& res) {
visit[u] = true;
int currComponentNode = 0;
for (int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if (!visit[v]) {
int subtreeNodeCount = dfs(g, v, visit, res);
if (subtreeNodeCount % 2 == 0)
res++;
else
currComponentNode += subtreeNodeCount;
}
}
return (currComponentNode + 1);
}
int maxEdgeRemovalToMakeForestEven(vector<int> g[], int N) {
bool visit[N + 1];
for (int i = 0; i <= N; i++)
visit[i] = false;
int res = 0;
dfs(g, 0, visit, res);
return res;
}
void addEdge(vector<int> g[], int u, int v) {
g[u].push_back(v);
g[v].push_back(u);
}
int main() {
int edges[][2] = {{0, 2}, {0, 1}, {0, 4}, {2, 3}, {4, 5}, {5, 6}, {5, 7} };
int N = sizeof(edges)/sizeof(edges[0]); vector<int> g[N + 1];
for (int i = 0; i < N; i++)
addEdge(g, edges[i][0], edges[i][1]);
cout << "Answer = " << maxEdgeRemovalToMakeForestEven(g, N) << endl;
return 0;
}輸出
Answer = 2
更新於： 31-Dec-2019
339 次瀏覽
廣告