可爱奶龙，带到班后就被虐待了，现在失踪了/ll
竞赛图（Tournament）的定义
对于一个任意两点恰有一条边的有向图称为「竞赛图」。
由于边集恰好描述了两两点之间的关系，可以视作「输赢」，故称之为「竞赛图」。
竞赛图的一些性质
1. 缩点后呈链状
注意，这里的「链状」不代表是一条链。
考虑缩点后任一点起做拓扑排序，对于不在同一强连通分量的两点 $u,v$，假设 $u$ 的拓扑序先于 $v$，必然存在边 $u\to v$。
将形成公差为 $1$ 的拓扑序形成的作为主链，支链为存在拓扑序差更大的边。如下图，就是缩点后竞赛图的一个示例。
2. Camion-Moon 定理
强连通竞赛图一定有 Hamilton 回路。换句话说，竞赛图的一个强连通分量内有 Hamilton 回路。
考虑归纳，$n=1$ 显然正确。在 $n>1$ 时，假设 $n-1$ 已经形成 Hamilton 回路。由于 $n$ 加入后仍强连通，说明至少存在一对 $(u,v)$ 使得有边 $u\to n,n\to v$。插入即可，由于回路的结构，这显然仍呈回路。
3. Reidi 定理
竞赛图一定有 Hamilton 路径。
先缩点，然后用性质 2 找到一条 Hamilton 回路，再在通向下一个强连通分量点后断裂，形成 Hamilton 路径。顺次相接，即可找到一条 Hamilton 路径。
4. 不小于 $3$ 的 SCC 中必然存在三元环
考虑归纳，$n=3$ 时显然。$n>3$ 时，存在 Hamilton 通路 $1\to 2\to3\to\cdots\to n$（不一定是点的原始编号）。若存在 $3\to 1$，就结束了。不存在，说明有 $1\to 3$。把 $2$ 去掉，如此转化为 $n-1$ 的情况。由于 $n-1$ 存在，则此情况必然存在。
5. Landau 定理
给定不降的非负整数序列 $p$，使 $\sum\limits_{i=1}^np_i=\dbinom n2$。存在竞赛图使得节点出度为 $p_1,p_2,\cdots,p_n$ 的充要条件为：$\forall i\in[1,n],\sum\limits_{j=1}^ip_j\ge\dbinom i2$。
若对于任意 $i\in[1,n-1]$，都有 $\sum\limits_{j=1}^i p_i>\dbinom i2$，当且仅当该竞赛图强连通。
必要性：显然。
充分性：考虑调整法。找出一个出度序列为 ${0,1,\cdots,n-1}$ 的 $n$ 阶竞赛图，显然可以构造。每次找位置最靠前的 $a_x<p_x$，在找最小的 $a_y>p_y$。二者求和相同，故 $y>x$。故 $a_y>p_y\ge p_x>a_x$，于是 $a_y\ge a_x+2$。差为 $2$，则必然存在边 $y\to i,i\to x$，反向即可实现 $a_x\gets a_x+1,a_y\gets a_y-1$。如此调整，易使 $a=p$。
例题
P3561 [POI 2017] Turysta
给出竞赛图，求从每个点出发最长的不重点路径。$n\le2000$。
竞赛图中的强连通分量内必然有 Hamilton 回路，从每个点所在强连通分量内开始，按照拓扑序向后找回路即可，任意一个点都可直接到达下一个 SCC。难点在于构造方案。
CF1268D Invertation in Tournament
给出竞赛图，可以选择任意个点，使与该点相连的边方向翻转。求在使其变成强连通图的翻转最少次数，以及在此前提下的合法方案数。$n\le 2000$。
考虑原图形成的强连通分量数，假设有 $k$ 个。拓扑排序后，按照拓扑序从小到大排序，称第 $i$ 小的为「第 $i$ 强连通分量」。
$k=1$
无需操作，答案为 0 1。
$k\ge 3$
显然只要取第 $i\in[2,k-1]$ 强连通分量中任意一点取反即可。
$k=2$
引理：大小为 $n\ge 4$ 的强连通竞赛图中，必然存在大小为 $n-1$ 的强连通竞赛子图。
证明：考虑 Camion-Moon 定理，该强连通竞赛图存在 $n$ 阶 Hamilton 回路。设回路为 $p_1\to p_2\to\cdots\to p_n\to p_1$，把 $p_1$ 从该图中删掉，形成的是 $p_2\to\cdots\to p_n$ 的 Hamilton 路径。讨论剩下形成的强连通分量（注意，竞赛图中不存在大小为 $2$ 的强连通分量）。
- 若存在 $k\ge 3$ 的强连通分量。此强连通分量中存在 Hamilton 回路，选长度 $k-1$ 的路径，接上 $p_1$ 即可形成 $n-1$ 的强连通竞赛子图。
- 若大小全为 $1$。只需删除非头尾的强连通分量，然后接上 $p_1$ 即可。
综上，无论何种情况，都可构造出大小为 $n-1$ 的强连通竞赛子图。
根据如上引理，可将大小 $n\ge 4$ 的强连通分量划分成大小分别为 $n-1$ 与 $1$ 的连通分量，只需翻转大小为 $1$ 的点即可。
然后对每个点都判一遍是否可行，这部分可以用 Landau 定理解决，复杂度为 $\mathcal O(n^2\log n)$。
Landau 定理：设 $p_i$ 为竞赛图的出度序列，从小到大排序后，若对于任意 $i\in[1,n-1]$，都有 $\sum\limits_{j=1}^i p_i>\dbinom i2$，当且仅当该竞赛图强连通。
剩余的情况只有 $k=2$ 且 $n\le 6$，这部分很少，直接暴力枚举即可。
AGC046F Forbidden Tournament
考虑一下竞赛图的性质，在缩完点后呈链状且大小 $\ge 3$ 的 SCC 必然存在三元环。考虑题目给的性质 3，如果存在 $\ge 3$ 的 SCC 必然是链的末端，否则 SCC 必然有不小于三元环连向同一个点。另外二元环的肯定不是竞赛图，所以图的形状只能是多个大小为 $1$ 的 SCC 从前往后连到最后一个复杂的 SCC。
然后考虑对这个复杂的 SCC 怎么计数，随便取内部一个点 $x$，把连向该点的其他点组成的集合设为 $I$，把该点所连向其他点组成的集合设为 $O$。讨论 $I,O$ 的性质。
显然，$I$ 中无环，否则就会破坏性质 3（前文已经提到竞赛图不存在二元环），而这些点相互有边，所以 $I$ 也是条链。再考虑一下 $O$，手玩一下最简单的情况，即 $\vert I\vert\le 1$，$\vert O\vert=3$ 且是一个三元环，发现无论如何都无法构造出合法情况，推广至更多的情况就是在此基础上加边加点，于是 $O$ 也是一条链。
对于这个团就十分清晰了，是 $I\to x\to O$ 链连点连链的结构，考虑 $I,O$ 之间的连边。设 $I_1,I_2,\cdots,I_p$，$O_1,O_2,\cdots,O_q$ 都是按照拓扑序排序后的序列。确定 $I_i$，那么向 $O$ 的连边，必然是 $I_i\to O_1,\cdots,O_{T_i}$，$O_{T_i+1},\cdots,O_{q}\to I_{i}$，否则必然会违反性质 3。另外，考虑 $T_i$ 的相对关系。若存在 $i<j$ 使得 $T_{i}>T_{j}$，考虑 $I_{i}\to O_{T_{j}+1}\to\cdots\to O_{T_i+1}\to I_i$ 的环，都有连向 $I_j$ 的边，必定非法。因此 $T$ 单调不降。
另外再考虑 $T$ 是否能构成强连通分量，只要保证 $O_q$ 能到 $I$ 即可，即 $T_1<q$。
接下来考虑性质 2，即最大入度为 $k$。$I_i$ 与 $O_i$ 的入度必须都 $\le k$。设该团前的链长为 $L$，$\vert I\vert=p$。考虑 $I_i$ 的入度不超过 $k$，有 $L+(i-1)+(n-L-1-p-T_i)\le k$，即 $T_i\ge n-p-k-2+i$。考虑 $O_i$ 的入度不超过 $k$，设首个 $j$ 使得 $T_j\ge i$，有 $L+1+p-j+1+i-1\le k$，即 $j\ge L+1+i+p-k$。于是 $i\le j+k-L-1-p$，故 $T_i\in[i+n-p-k-2,i+k-L-1-p]$。