Description

图论小王子小C经常虐菜,特别是在图论方面,经常把小D虐得很惨很惨。
这不,小C让小D去求一个无向图的最大独立集,通俗地讲就是:在无向图中选出若干个点,这些点互相没有边连接,并使取出的点尽量多。
小D虽然图论很弱,但是也知道无向图最大独立集是npc,但是小C很仁慈的给了一个很有特点的图: 图中任何一条边属于且仅属于一个简单环,图中没有重边和自环。小C说这样就会比较水了。
小D觉得这个题目很有趣,就交给你了,相信你一定可以解出来的。

Input

第一行,两个数n, m,表示图的点数和边数。
第二~m+1行,每行两个数x,y,表示x与y之间有一条无向边。

Output

输出这个图的最大独立集。
 
dfs一次断开每个环上最后被访问到的一条边,环上除了环的根以外所有点组成一条链
f0/f1表示一个点不选/不做强制要求时dfs子树内的最大独立集
g0/g1表示一个点不选/不做强制要求,但这个点所在的链的底部强制不选时dfs子树内的最大独立集
转移方式类似树形dp
#include<cstdio>
const int N=,R=;
char buf[R+],*ptr=buf-;
int n,m,ans=;
int et[],enx[],e0[N],ep=;
int ed[N],stk[N],stp=,bm[N],tp[N],dep[N];
int f0[N],f1[N],g0[N],g1[N];
inline int _int(){
int x=,c=*++ptr;
while(c<)c=*++ptr;
while(c>)x=x*+c-,c=*++ptr;
return x;
}
inline void maxs(int&a,int b){if(a<b)a=b;}
bool rt[N];
void dfs1(int w){
ed[w]=;
stk[++stp]=w;
for(int i=e0[w],u;i;i=enx[i])if(u=et[i]){
if(!ed[u]){
et[i^]=;
dep[u]=dep[w]+;
dfs1(u);
}else{
et[i]=et[i^]=;
while(dep[stk[stp]]>dep[u]){
int x=stk[stp--];
bm[x]=w;tp[x]=u;
}
}
}
if(stk[stp]==w)--stp;
}
void dfs2(int w){
f1[w]=;
if(w!=bm[w])g1[w]=;
for(int i=e0[w],u;i;i=enx[i])if(u=et[i]){
dfs2(u);
if(bm[u]!=bm[w]){
if(tp[u]!=w)g0[w]+=f1[u],g1[w]+=f0[u];
else g0[w]+=f1[u],g1[w]+=g0[u];
}else g0[w]+=g1[u],g1[w]+=g0[u];
if(tp[u]!=w)f0[w]+=f1[u],f1[w]+=f0[u];
else f0[w]+=f1[u],f1[w]+=g0[u];
}
maxs(f1[w],f0[w]);
maxs(g1[w],g0[w]);
}
int main(){
fread(buf,,R,stdin);
n=_int();m=_int();
while(m--){
int a=_int(),b=_int();
et[ep]=b;enx[ep]=e0[a];e0[a]=ep++;
et[ep]=a;enx[ep]=e0[b];e0[b]=ep++;
}
dfs1();dfs2();
printf("%d\n",f1[]);
return ;
}
04-04 10:41