【刷题】BZOJ 4316 小C的独立集

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;
}

【刷题】BZOJ 4316 小C的独立集

原文：https://www.cnblogs.com/hongyj/p/9562743.html