当前位置:网站首页>【学习笔记】图的连通性与回路
【学习笔记】图的连通性与回路
2022-07-05 14:10:00 【仰望星空的蚂蚁】
Graph Subset Problem
第一步删点挺妙的 。
如果一个点的度 < K-1 那么显然不会对答案造成贡献,可以用类似拓扑排序的过程把它删去 。
如果将度 <= K-1 的点删完后有剩余的话,可以解决 case 1 。
这题大小为 K 的团并不好找 。
我一开始的做法萎了
考虑在删掉度 = K-1 的点时判断这个点是否在一个团内 。
直接 O ( K 2 ) O(K^2) O(K2) 枚举是否两两有边 。
稍微算一下会发现时间复杂度 O ( m m log n ) O(m\sqrt{m}\log n) O(mmlogn) 。
细节:当一个点出队时才删除这个点以及和它相邻的边,注意一个点不要入队多次 。
Tanya and Password
拆点搞一搞会发现这题就是叫你求欧拉路 。
可以用栈模拟,考虑一个点走不动后,把这条路径倒序压进答案中 。
细节:注意判断图的联通性,因为是有向图所以检查最终序列的长度比较方便。
一定要先判节点的度啊啊啊啊啊啊啊啊啊啊
Data Center Drama
不会
刚开始想歪了 。
其实看到出度入度为偶数的限制很容易想到欧拉回路 。
问题在于欧拉回路保证出度 = 入度,不保证出入度为偶数 。
考虑将欧拉回路中的偶数边取反,这样除终点外路径上经过的点一定满足限制 。
最后判断边的总数,如果为奇数则在起点连一个自环即可 。
边栏推荐
- Recommendation number | what are interesting people looking at?
- What is the future development trend of neural network Internet of things
- Getting started with rce
- 关于Apache Mesos的一些想法
- ASP.NET大型外卖订餐系统源码 (PC版+手机版+商户版)
- 判断变量是否为数组
- 2022 construction welder (special type of construction work) special operation certificate examination question bank and online simulation examination
- 区间 - 左闭右开
- 强联通分量
- TDengine 社区问题双周精选 | 第三期
猜你喜欢
Postman简介、安装、入门使用方法详细攻略!
Tidb DM alarm DM_ sync_ process_ exists_ with_ Error troubleshooting
Why do mechanical engineers I know complain about low wages?
清大科越冲刺科创板:年营收2亿 拟募资7.5亿
非技术部门,如何参与 DevOps?
The IPO of Ruineng industry was terminated: the annual revenue was 447million and it was planned to raise 376million
Tiflash compiler oriented automatic vectorization acceleration
Current situation, trend and view of neural network Internet of things in the future
How to deeply understand the design idea of "finite state machine"?
Mingfeng medical sprint technology innovation board: annual revenue of 350million yuan, proposed to raise 624million yuan
随机推荐
怎么叫一手一机的功能方式
Assembly language
2022 driller (drilling) examination question bank and simulation examination
物联网应用技术专业是属于什么类
LeetCode_67(二进制求和)
Mingfeng medical sprint technology innovation board: annual revenue of 350million yuan, proposed to raise 624million yuan
Use the word "new" to attract curious people
ASP.NET大型外卖订餐系统源码 (PC版+手机版+商户版)
[buuctf.reverse] 152-154
魅族新任董事长沈子瑜:创始人黄章先生将作为魅族科技产品战略顾问
Google EventBus 使用详解
Sqllab 1-6 exercise
Faire un clip vidéo auto - média deux fois, comment clip n'est pas considéré comme une infraction
01. Solr7.3.1 deployment and configuration of jetty under win10 platform
昆仑太科冲刺科创板:年营收1.3亿拟募资5亿 电科太极持股40%
LeetCode_69(x 的平方根 )
TDengine 社区问题双周精选 | 第三期
Guofu hydrogen energy rushes to the scientific and Technological Innovation Board: it plans to raise 2billion yuan, and 360million yuan of accounts receivable exceed the revenue
Judge whether the variable is an array
Postman简介、安装、入门使用方法详细攻略!