题目概述

图论小王子小C经常虐菜，特别是在图论方面，经常把小D虐得很惨很惨。

这不，小C让小D去求一个无向图的最大独立集，通俗地讲就是：在无向图中选出若干个点，这些点互相没有边连接，并使取出的点尽量多。小D虽然图论很弱，但是也知道无向图最大独立集是npc，但是小C很仁慈的给了一个很有特点的图： 图中任何一条边属于且仅属于一个简单环，图中没有重边和自环。小C说这样就会比较水了。

小D觉得这个题目很有趣，就交给你了，相信你一定可以解出来的。

解题报告

先建出圆方树，然后考虑树形DP。定义 $f_{i,0/1}$ 表示 $i$ 点是否选择的最大独立集，并且对于方点，将 $f_{i,0/1}$ 定义为与方点 $i$ 的顶点相邻的节点是否选择的最大独立集。

那么圆点就正常进行最大独立集DP，而方点需要进行进一步DP。

由于DFS树建圆方树时是按照深度顺序建边的，因此对于方点，按照加边顺序获取出所有儿子即为环上的顺序。定义 $F_{i,0/1,0/1}$ 表示前 $i$ 个节点中，第 $i$ 个节点是否选择，并且第一个节点是否选择的最大独立集。这样定义是因为更新方点信息时，我们需要用到第一个以及最后一个的状态。

最后 $\max\{f_{1,0},f_{1,1}\}$ 就是答案。

示例程序

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=100000,maxm=120000;

int n,N,m,dfn[maxn+5],fa[maxn+5],lst[maxn+5];bool vis[maxm+5];
int E,lnk[maxn+5],nxt[maxm+5],son[maxm+5];
vector<int> e[maxn+5];int f[maxn][2],F[maxn+5][2][2];

inline void Add(int x,int y) {son[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void Cactus(int x,int pre=0){
    dfn[x]=++dfn[0];
    for (int j=lnk[x],u;j;j=nxt[j])
        if ((u=son[j])!=pre)
            if (!dfn[u]) fa[u]=x,lst[u]=j,Cactus(u,x); else
            if (dfn[u]<dfn[x]){
                N++;e[u].push_back(N);vis[j]=vis[j^1]=true;
                for (int i=x;i!=u;i=fa[i])
                    e[N].push_back(i),vis[lst[i]]=vis[lst[i]^1]=true;
            }
}
void DP(int x){
    int si=e[x].size();
    for (int j=0;j<si;j++) DP(e[x][j]);
    if (x>n){
        for (int i=0;i<2;i++)
            for (int j=0;j<2;j++)
                F[0][i][j]=(i==j?f[e[x][0]][i]:-1e9);
        for (int i=1;i<si;i++)
            for (int j=0;j<2;j++){
                F[i][j][0]=max(F[i-1][j][0],F[i-1][j][1])+f[e[x][i]][0];
                F[i][j][1]=F[i-1][j][0]+f[e[x][i]][1];
            }
        f[x][0]=F[si-1][0][0];
        f[x][1]=-1e9;
        for (int i=0;i<2;i++)
            for (int j=0;j<2;j++)
                f[x][1]=max(f[x][1],F[si-1][i][j]);
    } else {
        for (int j=0;j<si;j++) f[x][1]+=f[e[x][j]][0];f[x][1]++;
        for (int j=0;j<si;j++) f[x][0]+=max(f[e[x][j]][0],f[e[x][j]][1]);
    }
}
int main(){
    scanf("%d%d",&n,&m);N=n;E=1;
    for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x);
    Cactus(1);
    for (int i=1;i<=n;i++)
        for (int j=lnk[i];j;j=nxt[j])
            if (!vis[j] && dfn[son[j]]>dfn[i]) e[i].push_back(son[j]);
    DP(1);printf("%d\n",max(f[1][0],f[1][1]));
    return 0;
}