若竞赛图中有环，则一定构成三元环
若竞赛图中有环，则一定构成三元环
本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135099517
考虑一个 元环，肯定有弦。
我们就可以通过这个弦不断把环缩小即可。
同时竞赛图中不存在两个点的强连通分量。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 zhangxixi的博客！
相关推荐
2023-12-20
竞赛图及其缩点成链、强连通分量相关性质：CF1268D
竞赛图及其缩点成链、强连通分量相关性质：CF1268D 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135110596 考虑如何判断一个竞赛图是否强联通。 如果一个竞赛图不强联通，说明其存在一个子图，满足这个子图没有入边 / 出边。 我们以没有出边的情况来讨论。首先大小为 nnn 的子图之间至少产生 n(n−1)2\frac {n(n-1)}22n(n−1) 个出度，因为没有出度，所以我们就令其出度为这个就行了。从贪心角度考虑，我们直接按出度排序即可。 ...
2023-12-20
竞赛图缩点后成链状（拓扑序唯一）
竞赛图缩点后成链状（拓扑序唯一） 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132993089 一个常见结论 竞赛图缩点后必然成链状。 不是真正的链，只是类似链的偏序关系。
2023-09-18
拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d
拆贡献算总和（抓住双射）+竞赛图与连通分量相关计数：arc163_d 本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/132994501 https://atcoder.jp/contests/arc163/tasks/arc163_d 首先竞赛图有个性质： 然后有了这个性质，我们就可以考虑计数题的经典套路，拆贡献算总和。 考虑假如我们成功划分成两个集合 A,BA,BA,B ，其中一个可以为空（我们可以令 AAA 可以为空，防止算重），我们就记为算到一个新的...