Problem 18: Maximum Independent Set in a Tree
Problem Statement: Given a tree, find the size of the maximum independent set using tree DP.
Input
The first line contains n, the number of nodes. Next n-1 lines contain two integers u and v representing an edge.
Output
Print the size of the maximum independent set.
Examples
Input:
5
1 2
1 3
3 4
3 5
Output:
3
Solution Explanation
Method 1: Use tree DP where for each node you calculate two values: one when the node is included and one when it is excluded. Method 2: Use recursion to explore subsets of nodes, but the DP approach is more efficient and avoids recomputation.
Solution in C++
#include
#include
#include
using namespace std;
int n;
vector> adj;
vector> dp;
void dfs(int u, int p){
dp[u][0] = 0; // exclude u
dp[u][1] = 1; // include u
for(auto v : adj[u]){
if(v == p) continue;
dfs(v, u);
dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];
}
}
int main(){
cin >> n;
adj.resize(n+1);
dp.assign(n+1, vector(2,0));
for(int i=1;i> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
dfs(1,-1);
cout << max(dp[1][0], dp[1][1]);
return 0;
}