题目：http://acm.hdu.edu.cn/showproblem.php?pid=6736
思路：dfs+栈 判环
设图中环的大小分别为 c1, c2, ..., ck，不属于任何一个环的 边数为 b，则答案为：
( 2 ^ c1 - 1 ) * ( 2 ^ c2 - 1 ) * ......* ( 2 ^ ck - 1 ) * 2 ^ b
dfs判环时 各点入栈 若点已存在于栈中 则存在环 计算环大小即可 不必出栈
跑一遍连通图即可计算出所有环
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn=3e6+5; const int mod=998244353; vector<int>edge[maxn]; int vis[maxn],ins[maxn],s[maxn]; int top; int n,m; ll ans; void init() { ans=1; memset(vis,0,sizeof vis); memset(ins,0,sizeof ins); for(int i=1;i<=n;i++) edge[i].clear(); top=0; } ll qPow(ll n,int a) { ll res=1; while(a) { if(a&1) res=res*n%mod; n=n*n%mod; a>>=1; } return res; } void dfs(int u,int pre) { s[++top]=u; ins[u]=1; vis[u]=1; for(auto x:edge[u]) { if(!vis[x]) dfs(x,u); else if(ins[x]&&x!=pre) { int t=top; int sum=1; while(s[t]!=x) { t--; sum++; } m-=sum; ans=ans*(qPow(2,sum)-1+mod)%mod; } } ins[s[top]]=0; top--; } int main() { int a,b; while(~scanf("%d%d",&n,&m)) { init(); for(int i=0;i<m;i++) { scanf("%d%d",&a,&b); edge[a].push_back(b); edge[b].push_back(a); } for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,i); printf("%lld\n",ans*qPow(2,m)%mod); } return 0; }