Description
图论小王子小C经常虐菜，特别是在图论方面，经常把小D虐得很惨很惨。
这不，小C让小D去求一个无向图的最大独立集，通俗地讲就是：在无向图中选出若干个点，这些点互相没有边连接，并使取出的点尽量多。
小D虽然图论很弱，但是也知道无向图最大独立集是npc，但是小C很仁慈的给了一个很有特点的图： 图中任何一条边属于且仅属于一个简单环，图中没有重边和自环。小C说这样就会比较水了。
小D觉得这个题目很有趣，就交给你了，相信你一定可以解出来的。
Input
第一行，两个数n， m，表示图的点数和边数。
第二~m+1行，每行两个数x，y，表示x与y之间有一条无向边。
Output
输出这个图的最大独立集。
Sample Input
5 6
1 2
2 3
3 1
3 4
4 5
3 5
Sample Output
2
HINT
100% n <=50000, m<=60000
Solution
【刷题】BZOJ 1487 [HNOI2009]无归岛的弱化版，相当于点权为1
#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=50000+10,MAXM=60000+10,inf=0x3f3f3f3f;
int n,m,e,to[MAXM<<1],nex[MAXM<<1],beg[MAXN],DFN[MAXN],LOW[MAXN],f[MAXN][2],g[MAXN][2],ex[2],ans,a[MAXN],cnt,fa[MAXN],Visit_Num;
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
inline void insert(int x,int y)
{
to[++e]=y;
nex[e]=beg[x];
beg[x]=e;
}
inline void loop(int root,int x)
{
a[cnt=1]=x;
for(register int i=x;i!=root;i=fa[i])a[++cnt]=fa[i];
g[x][0]=f[x][0],g[x][1]=-inf;
for(register int i=2;i<=cnt;++i)
{
g[a[i]][0]=f[a[i]][0]+max(g[a[i-1]][0],g[a[i-1]][1]);
g[a[i]][1]=f[a[i]][1]+g[a[i-1]][0];
}
ex[0]=g[root][0],ex[1]=g[root][1];
g[x][1]=f[x][1],g[x][0]=f[x][0];
for(register int i=2;i<=cnt;++i)
{
g[a[i]][0]=f[a[i]][0]+max(g[a[i-1]][0],g[a[i-1]][1]);
g[a[i]][1]=f[a[i]][1]+g[a[i-1]][0];
}
chkmax(ex[0],g[root][0]);
f[root][0]=ex[0],f[root][1]=ex[1];
}
inline void Tarjan(int x,int p)
{
DFN[x]=LOW[x]=++Visit_Num;fa[x]=p;
f[x][1]=1;f[x][0]=0;
for(register int i=beg[x];i;i=nex[i])
if(to[i]==p)continue;
else if(!DFN[to[i]])
{
Tarjan(to[i],x);
chkmin(LOW[x],LOW[to[i]]);
if(LOW[to[i]]>DFN[x])
{
f[x][0]+=max(f[to[i]][1],f[to[i]][0]);
f[x][1]+=f[to[i]][0];
}
}
else if(DFN[to[i]]<DFN[x])chkmin(LOW[x],DFN[to[i]]);
for(register int i=beg[x];i;i=nex[i])
if(to[i]==p)continue;
else if(fa[to[i]]!=x&&LOW[to[i]]<=DFN[x]&&DFN[to[i]]>DFN[x])loop(x,to[i]);
}
int main()
{
read(n);read(m);
for(register int i=1;i<=m;++i)
{
int u,v;read(u);read(v);
insert(u,v);insert(v,u);
}
for(register int i=1;i<=n;++i)
if(!DFN[i])Tarjan(i,0),ans+=max(f[i][0],f[i][1]);
printf("%d\n",ans);
return 0;
}