2019 CCPC 重现赛 1006 基环树

• 2019 年 10 月 10 日
• 筆記

版权声明：本文为博主原创文章，遵循 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("%lldn",ans);  	return 0;  }