题解：CF1268D Invertation in Tournament

非常 $\text{educational}$ 的题，要求对竞赛图有很高的理解。

竞赛图十分稠密，因此我们猜测答案不大，并试图证明答案的上界。

先对图缩点，缩点之后是一条由若干 $\text{scc}$ 构成的链。可以看出，若该链长度 $\geq 3$，则答案不大于 $1$（对链中间的任意一个 $\text{scc}$ 的任意一个点操作即可）。同时由经典结论，大小为 $k$ 的强连通竞赛图存在长度 $\in [3, k]$ 的环。结合两点可得 $n > 6$ 是答案是 $1$。

（这一段可以跳过）经典结论的证明：考虑归纳证明，首先 $k$ 元环和 $3$ 元环一定存在，再考虑推 $k \to k - 1$。在环上去掉一个点 $x$，假设剩下的还是个 $\text{scc}$，直接证毕；否则由于剩下 $k - 1$ 个点构成若干 $\text{scc}$，其中每个 $\text{scc}$ 都有哈密顿回路，容易讨论出一个包含 $x$ 的 $k - 1$ 元环。

$n > 6$ 时，枚举操作哪一个点，并用兰道定理的推论：$cnt = \sum_{i = 1}^{n} [(\sum_{j = 1}^{i} s_j) = {i \choose 2}]$ 求解。其中 $s$ 是排序后的出度序列，$cnt$ 是 $\text{scc}$ 的个数。