[BZOJ4316]小C的独立集——仙人掌最大独立集

[BZOJ4316]小C的独立集

先把环上的分支处理掉，结果保留到环的点上。再处理环形DP，在tarjan的过程开个栈，环从栈中弹出来，一定要注意弹环的边界不能用x，因为x还可能先走到了其它环中。

#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
const int M=6e4+10;
int head[N],ver[2*M],nex[2*M],tot=1;
inline void add(int x,int y){
    ver[++tot]=y,nex[tot]=head[x],head[x]=tot;
}
int dfn[N],low[N],num,stk[N],top,dp[N][2];
void tarjan(int x,int fa) {
    dfn[x]=low[x]=++num;
    stk[++top]=x;
    dp[x][1]=1;
    for(int i=head[x]; i; i=nex[i]) {
        int y=ver[i];
        if(!dfn[y]) {
            tarjan(y,x);
            low[x]=min(low[x],low[y]);
            if(low[y]>dfn[x]) {
                --top;
                dp[x][0]+=max(dp[y][0],dp[y][1]);
                dp[x][1]+=dp[y][0];
            }else if(low[y]==dfn[x]){
                int t=stk[top--];
                int f00=dp[t][0],f01=dp[t][1],f10=dp[t][0],f11=-1e9;
                int g00,g01,g10,g11;
                while(stk[top+1]!=y){//一定要注意不能用x判断
                    t=stk[top--];
                    g00=dp[t][0]+max(f00,f01);g01=dp[t][1]+f00;
                    g10=dp[t][0]+max(f10,f11);g11=dp[t][1]+f10;
                    f00=g00;f01=g01;f10=g10;f11=g11;
                }
                dp[x][0]+=max(f00,f01);
                dp[x][1]+=f10;
            }
        } else if(y!=fa)
            low[x]=min(low[x],dfn[y]);
    }
}
int main() {
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=0; i<m; ++i) {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    int ans=0;
    for(int i=1; i<=n; ++i)//不一定连通
        if(!dfn[i]){
            top=0;
            tarjan(i,0);
            ans+=max(dp[i][0],dp[i][1]);
        }
    printf("%d
",ans);
    return 0;
}