版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41603898/article/details/101621445
设图中环的大小分别为 c1, c2, ..., ck,不属于任何一个环的
边数为 b,则答案为:2^b* (2^c1 - 1)*...*(2^ck - 1)
#include<bits/stdc++.h>
using namespace std;
const int maxn = 3e5 + 10;
const int mod = 998244353;
typedef long long ll;
vector<int> g[maxn];
int t,n,m,tot = 0,sz = 0,cnt;
int dfn[maxn],f[maxn];
vector<int> pot[maxn];
void dfs(int u,int fa) {
dfn[u] = ++sz;
bool t = false;
for(int i = 0; i < g[u].size(); i++) {
int v = g[u][i];
if(v == fa) continue;
if(!dfn[v]) {
f[v] = u;
dfs(v,u);
} else if(dfn[v] < dfn[u]) continue;
else if(dfn[v] > dfn[u]) {
++cnt;
for(int p = v; p != u; p = f[p])
pot[cnt].push_back(p);
pot[cnt].push_back(u);
continue;
}
}
}
ll fpow(ll a,ll b) {
ll r = 1;
while(b) {
if(b & 1) r = r * a % mod;
a = a * a % mod;
b >>= 1;
}
return r;
}
int main() {
scanf("%d%d",&n,&m);
for(int i = 1; i <= m; i++) {
int u,v;
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
ll ans = 1;
for(int i = 1; i <= n; i++) {
if(!dfn[i]) {
dfs(i,0);
}
}
for(int i = 1; i <= cnt; i++) {
ans = ans * (fpow(2,pot[i].size()) - 1) % mod;
m -= pot[i].size();
}
ans = ans * fpow(2,m) % mod;
printf("%lld\n",ans);
return 0;
}