Forest Program(2019ccpc秦皇岛F）

题：http://acm.hdu.edu.cn/showproblem.php?pid=6736

题意：删掉一些边使得图不存在点双，求方案数。

分析：若一条边不属于点双，那么这条边有删和不删俩种选择，若找到点双，点双中必须删掉一条边（题目有保证一条边只能属于一个点双，所以不用担心一条边用于多个点双）tarjan找点双，若为点双则必须删掉点双中的一条边

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define pii pair<int,int>
const int M=3e5+5;
const int mod=998244353;
vector<int>g[M];
//vector<pii>bcc[M];
pii stk[M];
int low[M],dfn[M],tot,top,cnt;
ll countt[M];
void tarjan(int u,int f){
    low[u]=dfn[u]=++tot;
    for(int i=0;i<g[u].size();i++){
        int v=g[u][i];
        pii e=make_pair(u,v);
        if(!dfn[v]){
            stk[++top]=e;
            tarjan(v,u);
            low[u]=min(low[u],low[v]);
            if(low[v]>=dfn[u]){
                cnt++;
                int len=top;
                while(stk[top]!=e){
                    //bcc[cnt].pb(stk[top--]);
                    top--;
                }
                //bcc[cnt].pb(stk[top--]);
                top--;
                countt[cnt]=len-top;
            }
        }
        else if(v!=f){
            if(dfn[v]<dfn[u])
                stk[++top]=e,low[u]=min(low[u],dfn[v]);
        }
    }
}
ll ksm(ll a,ll b){
    ll t=1ll;
    while(b){
        if(b&1)
            t=(t*a)%mod;
        b>>=1;
        a=(a*a)%mod;
    }
    return t;
}
ll mi[M];
int main(){
    for(int i=0;i<=M-5;i++)
        mi[i]=ksm(2ll,1ll*i);
    //cout<<mi[3]<<endl;
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        tot=top=cnt=0;
        for(int i=0;i<=n;i++)
            low[i]=dfn[i]=0,countt[i]=0,g[i].clear();
        for(int i=1;i<=m;i++){
            int u,v;
            scanf("%d%d",&u,&v);
            g[u].pb(v);
            g[v].pb(u);
        }
        for(int i=1;i<=n;i++)
            if(!dfn[i])
                tarjan(i,-1);

        ll ans=1ll;
    //    cout<<"cnt"<<cnt<<endl;
        for(int i=1;i<=cnt;i++){
            if(countt[i]>1){
                ans*=mi[countt[i]]-1;
                m-=countt[i];
                ans%=mod;
            }

        }
        if(m>=1)
            ans*=mi[m];
        printf("%lld\n",ans%mod);
    }
    return 0;
}

View Code

经验：得重新认识点双和边双，清楚定义