题意：
给出仙人掌图，问有多少种删边的方案使得该图变为一个森林。
思路：
跟上题类似。
从每个环出发考虑方案数，长度为t的环的方案数为2 t − 1，都不删的情况要减去，对于剩下的非环边，有删和不删两种选择，再乘上2 x , x =非环边的数量。
代码：
#include<bits/stdc++.h> using namespace std; typedef long long ll;typedef unsigned long long ull; typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD; #define I_int ll inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;} #define read read() #define rep(i, a, b) for(int i=(a);i<=(b);++i) #define dep(i, a, b) for(int i=(a);i>=(b);--i) ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;} const int maxn=3e5+100,inf=0x3f3f3f3f,mod=998244353; vector<int>g[maxn]; int n,m,vis[maxn],siz[maxn]; vector<int>w; void dfs(int u,int sum,int fa){ vis[u]=1; siz[u]=sum; for(auto t:g[u]){ if(t==fa) continue; if(!vis[t]) dfs(t,sum+1,u); else if(vis[t]==1){ w.push_back(siz[u]-siz[t]+1); } } vis[u]=2; } int main(){ while(cin>>n>>m){ rep(i,1,n) g[i].clear(),siz[i]=vis[i]=0; w.clear(); rep(i,1,m){ int u=read,v=read; g[u].push_back(v); g[v].push_back(u); } rep(i,1,n){ if(!siz[i]) dfs(i,1,0); } ll ans=1,tot=0; for(auto t:w){ // cout<<t<<endl; tot+=t; ans=(ans*(ksm(2,t,mod)-1+mod))%mod; } ans=ans*ksm(2,m-tot,mod)%mod; cout<<ans<<endl; } return 0; }
