竞赛图及其缩点成链、强连通分量相关性质：CF1268D

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135110596

考虑如何判断一个竞赛图是否强联通。

如果一个竞赛图不强联通，说明其存在一个子图，满足这个子图没有入边 / 出边。

我们以没有出边的情况来讨论。首先大小为 $n$ 的子图之间至少产生 $\frac {n(n-1)}2$ 个出度，因为没有出度，所以我们就令其出度为这个就行了。从贪心角度考虑，我们直接按出度排序即可。

之前一篇博客中提到，若竞赛图中存在环，则必然有大小为三的环。其实可以推广，我们把强连通中的哈密顿回路视为一个环，则必然存在一个点去掉后剩下仍然为强联通，也就是：

当 $M ≥ 4$ 时， $M$ 个点的强连通竞赛图一定有一个 $M − 1$ 个点的
导出子图，满足它也是强连通竞赛图。

因此我们现在可以开始构造了。

假设存在一个大小 $\ge 4$ 的强联通，我们直接把多余那个点抽出来翻转即可：

如果存在三个以上的连通块，我们可以中间连通块抽个点来翻转：

如果都不满足，则 $\le 2$ 个连通块，每个大小 $\le 3$ ，因此总点数 $le 6$ ，我们按数据点分治即可。