欧拉图和欧拉回路判定小结
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16352894.html
注意：下面讨论中的连通是不考虑孤立点的
无向图判欧拉图
- 连通
- 所有点度数为偶数
无向图判欧拉路径
- 连通
- 可以有两个点度数，其它点度数为偶数
有向图判欧拉图
- 基图连通（有向边不考虑方向连通）
- 所有点入度等于出度
有向图判欧拉路径
- 基图连通
- 允许有一个点入度比出度大于且同时有个点出度比入度大1，其他点度数为偶数
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-08-03
无源汇上下界可行流
无源汇上下界可行流 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132091530 新建两个超级源、汇点。 原先是a->b，范围[c,d]。现在变成 S->b，c a->T，c a->b，d-c ZOJ2314ReactorCooling_网络流-个人编程笔记
2021-11-29
【Loj #10101. 「一本通 3.6 练习 2」嗅探器】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15621588.html 题目链接 首先如果一个点满足答案，则这个点一定是割点。 然后我们可以从 aaa 点开始搜，对于每一个点，如果 bbb 点在它的儿子内，说明这个点分离了 aaa 和 bbb。 如何判断 bbb 是否在它的儿子内，只需要在搜索这个儿子前后判断一下即可。 Code 1234567891011121314151617181920212223242526272829303132333435363738394041424344454...
2026-06-18
一般图的点的三元问题转化为二分图最大独立集：ABC461G
一般图的点的三元问题转化为二分图最大独立集：ABC461G 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/162103270 https://atcoder.jp/contests/abc461/tasks/abc461_g 一种错误做法 我刚开始的做法： 首先每个点肯定是0、1013、2026，即0、1、2的。 考虑到每个点双内，它的最大值必然不会超过所有点选1。 于是建立圆方树，然后树上dp。 一个点若为2，则需同一点双内所有点均为0。 12345678...
2023-09-18
哈密顿回路
哈密顿回路 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132992984 哈密顿回路是一个经过所有节点恰好一次的回路。 相当于把欧拉回路定义中的边变成点
2022-04-25
【GDOI2022PJD2T4 机器人】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/16191401.html D2T4 机器人 题目 刚上初一的小纯特别喜欢机器人，这周末，她报名了学校的“小机器人俱乐部”，而进入俱乐部需要通过一场考试。 考试场地可以看作一个 n×mn \times mn×m 的网格图，行从上往下标号为 1,…,n1, \dots, n1,…,n，列从左往右标号为 1,…,m1, \dots , m1,…,m。每个格子有三种可能：空地，障碍物，机器人（有且只有一个），分别用“.”、“*”、“R”表示。现在小纯需要...
2021-11-17
【P2323 [HNOI2006]公路修建问题】题解
本文搬运自本人初中博客园博客，若图片加载不出来，可到原文查看：https://www.cnblogs.com/zhangtingxi/p/15568359.html 题目链接 题外话： 一道纯最小生成树的题，能出道蓝我也真服了… 本文默认使用kruskal算法，主要是因为另一种我不会 首先我们先满足 kkk 条一级道路，对所有道路按一级道路造价排序，然后用最小生成树的做法选出 kkk 条边。 对于剩下的道路按二级造价排序，然后同理继续选即可。 时间复杂度 O(nlogn)O(n\log n)O(nlogn) 需要注意的是题目输出格式有误，后面是输出具体方案。第一个数代表选的边的编...