BZOJ 4316: 小C的独立集 解题报告

4316: 小C的独立集

Description

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

这不，小C让小D去求一个无向图的最大独立集，通俗地讲就是：在无向图中选出若干个点，这些点互相没有边连接，并使取出的点尽量多。

小D虽然图论很弱，但是也知道无向图最大独立集是npc，但是小C很仁慈的给了一个很有特点的图： 图中任何一条边属于且仅属于一个简单环，图中没有重边和自环。小C说这样就会比较水了。

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

Input

第一行，两个数\(n\)，\(m\)，表示图的点数和边数。

第\(2\sim m+1\)行，每行两个数\(x\)，\(y\)，表示\(x\)与\(y\)之间有一条无向边。

Output

输出这个图的最大独立集。

HINT

\(100\%\) \(n\le 50000,m\le 60000\)

---

不用建圆方树的仙人掌。

最大独立集：选出最大的点集，使得两两没有边连接。

对普通树边按普通的\(dp\)即可

对环上的点，把环的头拽出来，然后从它屁股dp上去就行了

---

Code：

#include <cstdio>

const int N=6e4+10;

int head[N],to[N<<1],Next[N<<1],cnt;

void add(int u,int v)

{

    to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;

}

int min(int x,int y){return x<y?x:y;}

int max(int x,int y){return x>y?x:y;}

const int inf=0x3f3f3f3f;

int n,m,dp[N][2],dfn[N],low[N],dfsclock,fa[N];

void cal(int rt,int now)

{

    int t=now,s0=0,s1=0;

    while(now!=rt)

    {

        int tmp=s0;

        s0=max(s0,s1)+dp[now][0];

        s1=tmp+max(dp[now][1],dp[now][0]);

        now=fa[now];

    }

    dp[rt][0]+=max(s0,s1);

    s0=-inf,s1=0,now=t;

    while(now!=rt)

    {

        int tmp=s0;

        s0=max(s0,s1)+dp[now][0];

        s1=tmp+max(dp[now][1],dp[now][0]);

        now=fa[now];

    }

    dp[rt][1]+=s0;

}

void dfs(int now)

{

    dp[now][1]=1;

    dfn[now]=low[now]=++dfsclock;

    for(int v,i=head[now];i;i=Next[i])

        if((v=to[i])!=fa[now])

        {

            if(!dfn[v]) fa[v]=now,dfs(v),low[now]=min(low[now],low[v]);

            else low[now]=min(low[now],dfn[v]);

            if(dfn[now]<low[v])//正常树边

                dp[now][0]+=max(dp[v][0],dp[v][1]),dp[now][1]+=dp[v][0];

        }

    for(int v,i=head[now];i;i=Next[i])

        if(fa[v=to[i]]!=now&&dfn[v]>dfn[now])

            cal(now,v);

}

int main()

{

    scanf("%d%d",&n,&m);

    for(int u,v,i=1;i<=m;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);

    dfs(1);

    printf("%d\n",max(dp[1][0],dp[1][1]));

    return 0;

}

---

2018.12.24