专栏首页wym2019 CCPC 重现赛 1006 基环树

2019 CCPC 重现赛 1006 基环树

版权声明:本文为博主原创文章,遵循 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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 中国大学生程序设计竞赛 CCPC 落幕,清华夺冠!旷视承诺包揽未来 5 年赛事总赞助

    AI 科技评论按:经过 2018 年 11 月 24 — 25 日两日紧张的比赛,第四届中国大学生程序设计竞赛( CCPC )总决赛于 25 日落下帷幕,「清华...

    AI科技评论
  • 清华最强本科毕业生Top10出炉,从来没有什么天才学霸!

    根据清华大学官方消息,2020年清华大学特等奖学金(本科生)答辩会在11月12日下午举行。15位候选人完成答辩后,现场评委投票,选出了前10名单。

    开发者技术前线
  • 这些年,这些ACM大佬-施韩原访谈

    转载说明:这是一个ACM大佬的访谈系列,由Comet OJ平台在这两个月陆陆续续制作完成,本号经过Comet OJ同意进行转发,大家可以多学习学习前辈的经验~感...

    ACM算法日常
  • MySQL-长事务详解

    『入门MySQL』系列文章已经完结,今后我的文章还是会以MySQL为主,主要记录下近期工作及学习遇到的场景或者自己的感悟想法,可能后续的文章不是那么连贯,但还是...

    MySQL技术
  • PAT乙级题目答案汇总PAT (Basic Level) Practice (中文)

    专栏链接 https://blog.csdn.net/shiliang97/category_9294537_2.html

    韩旭051
  • 节点资本在BiYong圆桌论坛讨论区块链投资

    1、 首先请各位机构大佬回顾一下去年到今年各位所在的机构主要投资了哪些项目,同时也分享一下各自机构的投资逻辑和赛道。

    区块链技术布道
  • Ubuntu16.04安装TensorFlow2.x CPU和GPU必备指南

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    片刻
  • 从700多支队伍脱颖而出,知乎这个算法大赛冠军这样让大V「谢邀」答题

    知乎是目前国内最大的知识问答社区。截止 2019 年 1 月,它已经成为一个拥有 2.2 亿用户的平台。每天平台上都会产生大量的新提问,但是如此海量的问题往往不...

    机器之心
  • MySQL下的DB link

    在实际工作中,我们可能会遇到需要操作其他数据库实例的部分表,但又不想系统连接多库。此时我们就需要用到数据表映射。如同Oracle中的DBlink一般,使用过Or...

    MySQL技术

扫码关注云+社区

领取腾讯云代金券