【题解】Bzoj4316小C的独立集

　　决定要开始学习圆方树 & 仙人掌相关姿势。加油~~

　　其实感觉仙人掌本质上还是一棵树，长得也还挺优美的。很多的想法都可以往树的方面上靠，再针对仙人掌的特性做出改进。这题首先如果是在树上的话那么实际上就是没有上司的舞会。当出现了环的时候意味着我们需要针对环的存在做出特殊的处理。

　　还是设立状态 \(f[i][1/0]\) 表示在 \(i\) 的子树内（包括\(i\)）时选取 \(i\) 与不选取 \(i\) 的最大独立集大小。当转移发生在树边上的时候，直接转移。当不是树边的时候，我们可以将环上的点单独拿出来重新dp。实际上也就是要处理环上非树边的排斥关系，保证这层关系并转移。其实由于仙人掌上的环不包含，不交叉，很多的时候是类似于一棵基环树的（只不过环变多了？但不影响本质吧）。

　　判断树边/非树边的依据就是 \(dfn, low\) 等值的大小。而一个环的根与底部也同样可以运用dfs树的性质来解决。

#include <bits/stdc++.h>

using namespace std;

#define maxn 150000

#define INF 99999999

int n, m, cnp = , head[maxn];

int f[maxn][], fa[maxn];

int timer, dfn[maxn], low[maxn];

struct edge

{

    int to, last;

}E[maxn];

int read()

{

    int x = , k = ;

    char c;

    c = getchar();

    while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * k;

}

void add(int u, int v)

{

    E[cnp].to = v, E[cnp].last = head[u], head[u] = cnp ++;

    E[cnp].to = u, E[cnp].last = head[v], head[v] = cnp ++;

}

void DP(int S, int T)

{

    int f1 = , f0 = ;

    for(int i = T; i != S; i = fa[i])

    {

        int t1 = f1 + f[i][], t0 = f0 + f[i][];

        f0 = max(t1, t0); f1 = t0;

    }

    f[S][] += f0; f0 = , f1 = -INF;

    for(int i = T; i != S; i = fa[i])

    {

        int t1 = f1 + f[i][], t0 = f0 + f[i][];

        f0 = max(t1, t0); f1 = t0;

    }

    f[S][] += f1;

}

void dfs(int u, int gra)

{

    fa[u] = gra; dfn[u] = low[u] = ++ timer;

    f[u][] = , f[u][] = ;

    for(int i = head[u]; i; i = E[i].last)

    {

        int v = E[i].to;

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

        else if(v != gra) low[u] = min(low[u], dfn[v]);

        if(low[v] > dfn[u])

            f[u][] += f[v][], f[u][] += max(f[v][], f[v][]);

    }

    for(int i = head[u]; i; i = E[i].last)

        if(fa[E[i].to] != u && dfn[u] < dfn[E[i].to])

            DP(u, E[i].to);

}

int main()

{

    n = read(), m = read();

    for(int i = ; i <= m; i ++)

    {

        int u = read(), v = read();

        add(u, v);

    }

    dfs(, );

    printf("%d\n", max(f[][], f[][]));

    return ;

}