2019 CCPC 秦皇岛F 发表于 2019-10-30 | 分类于 ACM题解 | 阅读次数: 比赛时已经推出公式了, 问题是不会求环的个数。 公式这里就不写了,只是附上dfs + 时间戳的求环。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include <iostream>#include <algorithm>#include <math.h>#include <cstring>using namespace std;typedef long long ll;const ll mod = 998244353;vector<int>G[300005];int dln[300005], d[300005];int cnt ;void dfs(int now,int p){ dln[now] = dln[p] + 1; for(int i = 0; i < G[now].size(); ++i) { int v = G[now][i]; if(v == p) continue; if(dln[v] != 0){ if(dln[v] < dln[now]) d[++cnt] = dln[now] - dln[v] + 1; } else dfs(v, now); }}ll pow(ll a, ll b, ll mod){ ll ans = 1; while(b) { if(b & 1) ans = ans * a % mod; a = a * a % mod; b >>= 1; } return ans % mod;}int main(){ int n, m ,u, v; cin >> n >> m; cnt = 0; memset(dln, 0, sizeof(dln)); for(int i = 1 ; i <= m; ++i) { scanf("%d %d",&u,&v); G[u].push_back(v); G[v].push_back(u); } dfs(1, 0); // cout << cnt << '\n'; int edge = m; for(int i = 1; i <= cnt; ++i) { edge -= d[i]; } long long ans = pow(2, edge, mod); for(int i = 1; i <= cnt; ++i) { ll num = pow(2, d[i], mod); ll num1 = (num - 1 + mod) % mod; ans = (ans * num1) % mod; } cout << ans << '\n';} 打赏