洛谷
首先需要知道独立集是什么。
简单来讲独立集就是一个没有相邻的点的集合。
我们已经处理过比较多的独立集问题了。
比如常见的线性独立集。
代码：
for(int i=1;i<=n;i++){dp[i][0]=max(dp[i-1][1],dp[i-1][0]);dp[i][1]=dp[i-1][0]+a[i];
}
如果是一个环呢？
此时如果我们第一位选择了，那么最后一位就不能选择。
于是我们可以分第一位可以选和第一位不可以选两种情况。
代码：
dp[1][0]=0,dp[1][1]=a[1];
for(int i=2;i<n;i++){dp[i][0]=max(dp[i-1][1],dp[i-1][0]);dp[i][1]=dp[i-1][0]+a[i];
}
dp[n][0]=max(dp[n-1][1],dp[n-1][0]);
dp[1][0]=0,dp[1][1]=0;
for(int i=2;i<n;i++){dp[i][0]=max(dp[i-1][1],dp[i-1][0]);dp[i][1]=dp[i-1][0]+a[i];
}
dp[n][1]=dp[n-1][0]+a[n];
那么树上怎么处理？
代码：
void dfs(int p,int f){dp[p][1]=a[p];for(int i:e[p]){if(i==f)continue;dfs(i,p);dp[p][0]+=max(dp[i][0],dp[i][1]);dp[p][1]+=dp[i][0];}
}而这道题目是一个仙人掌，仙人掌的一个性质就是只有环和链，不存在两个环有公有部分的情况。
那么我们直接在图中找到环，得到这部分的最大独立集，然后继续向上处理答案即可。
那么我们此时只需要找到环就可以了。
无向图中环是一个点双连通分量，我们直接按照点双连通分量的规则去判定是否有环即可。
我们将环得到了单点的值以后再向上进行转移即可。
代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,dfn[50005],low[50005],cnt,id,st[50005],top,f[50005][2],tmp[50005],k;
vector<int> e[50005];
void tarjan(int p){f[p][1]=1;dfn[p]=low[p]=++cnt;st[++top]=p;for(int i:e[p]){if(!dfn[i]){tarjan(i);low[p]=min(low[p],low[i]);if(low[i]>=dfn[p]){k=0;do{tmp[++k]=st[top];top--;}while(st[top+1]!=i);int f1=f[tmp[1]][1],f0=f[tmp[1]][0],g1,g0;for(int i=2;i<=k;i++){g1=f1,g0=f0;f1=g0+f[tmp[i]][1],f0=max(g0,g1)+f[tmp[i]][0];}f[p][0]=max(f0,f1)+f[p][0];f1=0,f0=f[tmp[1]][0],g1,g0;for(int i=2;i<=k;i++){g1=f1,g0=f0;f1=g0+f[tmp[i]][1],f0=max(g0,g1)+f[tmp[i]][0];}f[p][1]=f0+f[p][1];}}else low[p]=min(low[p],dfn[i]);}
}
signed main(){cin>>n>>m;for(int i=1,x,y;i<=m;i++){cin>>x>>y;e[x].push_back(y);e[y].push_back(x);}tarjan(1);cout<<max(f[1][0],f[1][1]);return 0;
}