小C的独立集

Time Limit: 10 Sec Memory Limit: 128 MB

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

cz_xuyixuan的题解

建立圆方树，并进行树形DP。

对于圆点\(i\)，记\(f[i,0]\)表示不选取\(i\)，\(i\)子树的最大独立集，\(f[i,1]\)表示\(i\)子树的最大独立集。

对于方点\(i\)，记\(f[i,0]\)表示不选取与\(i\)的父亲相邻的圆点，\(i\)子树的最大独立集，\(f[i,1]\)表示\(i\)子树的最大独立集。

在方点处的转移需要做一个子动态规划。转移较为显然，此处不再赘述。

时间复杂度\(O(n)\)。感觉仙人掌DP题主要就是处理方点，让它对父亲可以像圆点一样更新。

#include<bits/stdc++.h>
#define co const
#define il inline
template<class T>T read(){
    T x=0,w=1;char c=getchar();
    for(;!isdigit(c);c=getchar())if(c=='-') w=-w;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    return x*w;
}
template<class T>T read(T&x){
    return x=read<T>();
}
using namespace std;

co int N=100000+10;
int n;
vector<int> e[N];
int pos[N],dfn;
// RST
int cir;
int fa[N],to[N],nx[N];
int f[N][2];

void tarjan(int x,int fa){
    static int st[N],top;
    st[++top]=x;
    pos[x]=++dfn;
    for(unsigned i=0;i<e[x].size();++i){
        int y=e[x][i];
        if(y==fa) continue;
        if(!pos[y]){
            ::fa[y]=x;
            tarjan(y,x);
        }
        else if(pos[y]<pos[x]){
            ++cir;
            ::fa[n+cir]=y,nx[n+cir]=to[y],to[y]=n+cir;
            for(int j=top;st[j]!=y;--j)
                ::fa[st[j]]=n+cir,nx[st[j]]=to[n+cir],to[n+cir]=st[j];
        }
    }
    --top;
}
void dp(int x){
    if(x<=n){
        f[x][1]=1;
        for(int y=to[x];y;y=nx[y]){
            dp(y);
            f[x][0]+=max(f[y][0],f[y][1]);
            f[x][1]+=f[y][0];
        }
        return;
    }
    // S
    for(int y=to[x];y;y=nx[y]) dp(y);
    static int tmp[N][2],tot;
    tmp[tot=1][0]=f[to[x]][0],tmp[tot][1]=0;
    for(int y=nx[to[x]];y;y=nx[y]){
        ++tot;
        tmp[tot][0]=max(tmp[tot-1][0],tmp[tot-1][1])+f[y][0];
        tmp[tot][1]=tmp[tot-1][0]+f[y][1];
    }
    f[x][0]=tmp[tot][0];
    tmp[tot=1][0]=f[to[x]][0],tmp[tot][1]=f[to[x]][1];
    for(int y=nx[to[x]];y;y=nx[y]){
        ++tot;
        tmp[tot][0]=max(tmp[tot-1][0],tmp[tot-1][1])+f[y][0];
        tmp[tot][1]=tmp[tot-1][0]+f[y][1];
    }
    f[x][1]=max(tmp[tot][0],tmp[tot][1]);
}
int main(){
    read(n);
    for(int m=read<int>(),x,y;m--;){
        read(x),read(y);
        e[x].push_back(y),e[y].push_back(x);
    }
    tarjan(1,0);
    dp(1);
    printf("%d\n",max(f[1][0],f[1][1]));
    return 0;
}

BZOJ4316 小C的独立集

原文：https://www.cnblogs.com/autoint/p/11248383.html