估计没什么用，所以只是娱乐向。
定义：\(n\) 个点，任意两点之间有且仅有一条有向边的图叫竞赛图，这个名称很形象吧。
-
一定存在一条哈密顿路径，存在哈密顿回路的充要条件是这个竞赛图强连通。
-
的每一个强连通都存在哈密顿环。数学归纳法证明。
-
缩点后是一条链。用上面那条性质可以证明。
-
若 \(x\) 的出度大于 \(y\) 的出度，则一定存在一条 \(x\) 到 \(y\) 的路径。利用缩点后是一条链证明。
-
竞赛图没有自环，没有二元环；若竞赛图存在环，则一定存在三元环。
-
兰道定理：将图每个点的出度排序，若 \(\forall k, \sum_{i=1}^kd_k \geqslant \binom k 2\)，且 \(k=n\) 时取等，那么这个图是竞赛图。反之也成立。
CF1498E Two Houses
发现竞赛图中如果入度大的点 \(x\) 可以到达入度小的点 \(y\)，则这两个点强联通。
证明：结合性质 \(x\) 的出度小于 \(y\) 的出度，所以 \(y\) 一定能到达 \(x\)。如果 \(x\) 能到达 \(y\)，就强联通了。
所以直接排序后从大到小询问即可。
也有一种 无需询问 的方法：我们将点的入度从小到大排序。如果前 \(k\) 个点，\(\sum d_i=\binom k 2\) ，设上一个这样的 \(k\) 为 \(las\)，那么 \([las+1,k]\) 是一个强联通分量。通过这种方式我们可以找出所有的强联通分量，所以直接计算答案。
证明：发现竞赛图中强联通分量的度数区间一定连续，这个可以通过想象缩点后的那条链得出。设第一个 SCC 为集合 \(L\)，大小为 \(l\)，后面的点为集合 \(R\)，大小为 \(r\)。则 \(L\) 的入度和为 \(\binom l 2\)，而 \(L\rightarrow R\) 的边有 \(lr=sum_{i\in R}l\) 个，所以减一下 \(R\) 内部的边有 \(\binom r 2\) 个，所以 \(R\) 是一个 SCC。至于 \(L+R\) 为什么不是 SCC，可以感性理解得出。
CF1514E Baby Ehab's Hyper Apartment
标签：缩点,竞赛,联通,出度,入度,笔记,学习,binom From： https://www.cnblogs.com/Kidulthood/p/17533535.html