给定树T = (V,E),求树的最大独立集。用C++设计一个高效的贪心算法来解决问题。
时间: 2024-02-13 20:01:46 浏览: 19
以下是基于贪心算法的 C++ 代码来求解树的最大独立集:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100005;
vector<int> adj[N];
int dp[N][2];
// 计算子节点的 dp 值
void dfs(int u, int fa) {
dp[u][1] = 1; // 选 u 节点
for (int v : adj[u]) {
if (v == fa) continue;
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]); // 不选 u 节点
dp[u][1] += dp[v][0]; // 选 u 节点,不选 v 节点
}
}
// 求最大独立集
vector<int> MIS(int n) {
dfs(1, 0);
vector<int> ans;
int mx = max(dp[1][0], dp[1][1]);
bool choose = dp[1][1] > dp[1][0];
for (int i = 1; i <= n; i++) {
if (dp[i][choose] == mx) {
ans.push_back(i);
mx--;
choose = !choose;
}
}
return ans;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n - 1; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> ans = MIS(n);
cout << "最大独立集为: ";
for (int x : ans) cout << x << " ";
cout << endl;
return 0;
}
```
时间复杂度为 O(n),其中 n 是树的节点数。