竞赛图六步走

本文为二十一世纪二十年代的最新产物，作者：[数据删除]

想转载这辈子都不用联系我了

本文内容可能过于空虚，建议先扫一遍，然后再分成几个部分每天读一部分，因为这样你才能掌握本文的精髓

竞赛图 是一个很没用的东西，好比数学中的 解 剖 青 蛙 。它也是信奥学习中的不用学习的点，因此把它学好啥用没有。如果你去洛谷等OJ上刷题你会明显感觉到：

竞赛图的题目我都能看得懂题解，但要我自己贺却没有思路。这时，贺的套路就凸显出了它的重要性。

套路如浩瀚的题海中的一座灯塔，指引我们解题的方向。 ——[数据删除]

网上其他的文章会叽里咕噜说一堆东西，常见的有

怎么SSH——怎么背下 ip 赋——ctrl cv

可你不妨设想一下，这种套路有实质的作用吗？ 没有，因为前两步会比第三步还要难写。

一、竞赛图六步走

注意：这 $6$ 步和所谓的 $SSH$ 完全不同，后面会讲到。

1. 贺
2. 贺
3. 贺
4. 贺
5. 贺
6. 贺

二、“六步走”的详解

PS：这部分博客会按照六个步骤分为六个小部分，每部分会以一个口诀结束，并会在下方有相应的解释，口诀的作用是方便各位大佬记忆 ，看我多贴心 。

${\tt}\Huge{[数据删除]大佬太有文采了但是我编不出来口诀，希望有人提供，谢谢}$

定义：$n$ 个点，任意两点之间有一条有向边的图

性质：（证明都是瞎写的不保证正确性

因为 $n=2$ 很奇怪，所以不算进下面的结论套路

1. 竞赛图一定存在一条哈密顿路径

   证明：考虑归纳， $n=1$ 的时候显然成立，现在已经求出 $n-1$ 个点的竞赛图的哈密顿路径了，发现如果第 $n$ 个点连出去的边都是指向其他点或者都是指向自己时，一定可以把这个点放到哈密顿路径首或尾，若不满足上面的条件，则一定存在 $u,v$ 满足有边 $(u,n),(n,v)$ ，直接把 $n$ 放到 $u,v$ 中间就好了

2. 竞赛图缩点后成链状

   这里的是呈链状，边都是从拓扑序小的连向拓扑序大的

   证明：发现缩点后还是一张竞赛图，因为竞赛图一定有哈密顿回路，所以呈链状

3. 竞赛图的每一个强连通分量都存在哈密顿回路

   证明：跟哈密顿路径考虑方法很像，归纳，$n=1$ 的时候显然成立，还是讨论边的指向，如果都是指向其他点或者都是指向自己时，发现这个点一定自己作为一个 $scc$ ，否则一定可以在他所在的 $scc$ 的环上找到两点 $u,v$ 使得边是 $(u,n),(n,v)$ ，这样一定可以加进去

4. 对于一个竞赛图中大小为 $n$ 的强连通分量，其一定存在大小为 $\forall len \in [1,n]$ 的简单环

   证明：考虑 $3$ 的证明，我们对于一个强连通分量是一个点一个点加的，每次加之前都会有环，加之后也有环，所以显然是对的

   因为竞赛图很傻逼，发现 $2$ 个点没有环，会影响到 $n=3$ 所以结论要求 $n \ge 4$ 😠

5. 如果 $u$ 的出度大于 $v$ 的出度，则 $u$ 一定可以到达 $v$

   证明：如果 $u,v$ 在一个强连通分量里面显然正确，当不在一个强连通分量时考虑缩点后的拓扑序

   设 $u$ 所在的强连通分量是 $x$，$v$ 所在的强连通分量是 $y$ （注意强连通分量编号是拓扑序倒序

   当 $x>y$ 时，缩点完成链状，显然可以到达

   当 $x<y$ 时，因为缩点完了已经没有环了，所以 $v$ 连出去的点一定是强连通分量标号小于 $y$ 的， $u$ 连出去的点一定是强连通分量标号小于 $x$ 的，又因为 $x<y$ ，所以得出 $u$ 出度小于 $v$ 出度，寄

6. 存在竞赛图满足每个点出度序列为 $arr$ 当且仅当将 $arr$ 排序后，$\forall k \sum\limits_{i=1}^{k} arr_i \ge {k \choose 2}$ 且 $\sum\limits_{i=1}^{n} arr_i = {n \choose 2}$ (兰道定理)

   证明：必要性显然

   充分性考虑构造，先让出边集合 $A$ 为 $0,1,2,3…n-1$ ，这显然是可以构造出来的，并且满足上面的条件，现在有一些点不满足，我们换一下边的指向顺序来满足这个条件，设 $x$ 为第一个不满足 $A_x=arr_x$ 的地方，$y$ 为最大的 $A_y=A_x$ ，$z$ 为最小的 $A_z>arr_z$ ，发现 $A_x < arr_x \le arr_y < A_z$ ，所以必定有一个点 $p$ 和 $x,z$ 的关系是边 $(p,x),(z,p)$ 现在只要 $swap$ 一下两条边指向就可以让 $A_x+1\rightarrow A_x,A_z-1\rightarrow A_z$ ，发现这个操作一定是可以一直进行的，所以我们就通过不断调整调整出 $arr$ 来了

   推论：一个竞赛图强连通当且仅当 $\not\exists 1\le k <n,\sum\limits_{i=1}^{k}arr_i={k\choose 2}$

   必要性：对于 $\forall k \in [1,n)$ ，因为我是极大强连通分量的一部分，所以一定有点会指向 $(k,n]$ 的点，又因为我前 $k$ 个点的导出子图是竞赛图，所以 $\sum\limits_{i=1}^{k}arr_i\ge{k\choose 2}+1$

   $\sum\limits_{i=1}^{k}arr_i>{k\choose 2}$

   条件可知前 $k$ 个点组成的导出子图边集大小为 ${k \choose 2}$，所以前 $k$ 个点没有指向后面的点的边，寄

   充分性：跟哈密顿回路很像，归纳，现在已经有 $k$ 个点了，现在加进来第 $k+1$ 个点 $y$ ，我们钦定这个点一定有一条 $\exists x\in S,(x,y)$ 的边，其中 $S$ 是当前选的选的 $k$ 个点的集合，发现加进来后一定是一个强连通分量，又因为给定条件，所以一定能一直找到这个点

坚持看完的都是大佬

建议各位大佬将本文收藏，多读几遍，口诀最好背过，这样效果最好。 本文的初衷是想让大佬们更加大佬化，WE AK NOIP！！！—— [数据删除] 大佬

Wait！！！

信奥中有一句通用法则：

题海战术

套路虽然有用，但是不结合题目来实战，就等于 0 ，我们一起来将这个竞赛图套路应用到实际解题当中： （ 竞赛图的核心其实不在思路这块，代码相对而言可以说是呼之欲出的，又限于篇幅，后面就重点讲怎么贺，代码就省略了哈 ）

1. 基础应用：牢固的壳子
2. 高级运用：熟练的互联网搜索能力
3. 赛场应用：$SSH$
4. 优化：还不赶紧让你贺的那个人优化

可能你会认为，博主直接复制粘贴一个标程，再敲点注释不是又省事又清楚吗？干嘛非要长篇大论讲一堆没用的这种心情很能理解，但是你要明白

不会自己贺出来题目的人，贺多少题都没用。信奥的学习是注重贺的，而不是注重自己做的。看了别人的题解得到启发确实可以马上 $AC$ ，但是考场上却不能，因为没有了别人的题解，没有过硬的 $SSH$ 能力，而本博客正是总结了“贺的套路”。 ——[数据删除] 大佬

后面我会从洛谷中精选一些绿题和蓝题进行讲解，并且每日更新至多 ${\tt}\Huge{0}$ 道题。

CF1268D Invertation in Tournament

结结结结结结结结结结结论题

首先先将竞赛图缩点，考虑操作几次可以把这张竞赛图变成一个强连通图

考虑随便找一个点 $u$ 翻转，假设他在的强连通分量是 $x$ ，发现他一定会向小于 $x$ 的强连通分量连边，而大于 $x$ 的强连通分量一定会向 $x$ 连边（ $tarjan$ 后强连通分量编号是拓扑序倒序），所以反转后就一定是强连通竞赛图了！

这样我们就做完了……吗？

发现好像有这么一种可能，我翻转 $u$ 之后 $x$ 会分裂成很多强连通分量，寄！

但是没有关系，因为我们有结论套路 $4$！，这样我们呢可以保证存在一个点 $u$ 使得翻转之后 $x$ 不会寄！

然后我们就做完了……吗？

万一根本没有强连通分量大小大于 $3$ 的就没有这个条件了 🤔

但是真的寄了吗？发现将一个大小为 $3$ 的强连通竞赛图翻转一个点相当于把他变成两条链，所以只要强连通分量大小小于等于 $3$ 的个数大于 $2$ 就没事了 🙃

好像 $3$ 个大小为 $1$ 的也会寄，不过没关系，我不想 🤔 了，发现好像要是有那么 $10$ 个点左右就没事了，开摆

题解说是 $7$ 个点，但是好像没有考虑我上面说的捏（但是上面的只有 $3$ 个点

要是不考虑这 $3$ 个大小为 $1$ 的情况，大概证明就是首先强连通分量个数大于 $2$ 或等于 $1$ 显然正确，要是大小为 $2$ ，那么肯定有一个连通块大小大于 $3$ ，赢！🙃

然后我们就做完了……吗？

好像真的做完了……

注意特判本来就是一个强连通竞赛图

发现 $tarjan$ 缩点是 $O(n+m)$ 的，寄 😅，不过没关系，还有一个兰道定理推论（结论套路 $6$）可以搞这个玩意

• 本次更新时间为2020.5.24
• 下次更新时间为2020.5.24

如果你认为本文对你有帮助的话，请素质三连，Thanks♪(･ω･)ﾉ