推销博客！

下面摘自博客

结论3

已知竞赛图所有点的 $in$，则可以确定每个强联通分量内包含的点。

证明：考虑按某种拓扑序遍历所有强联通分量，设遍历到的前若干个强联通分量里的所有点构成的集合为 $S$，则 $\dfrac{|S|(|S|-1)}{2}=\sum\limits_{x\in S} in_x$。因为按拓扑序，后遍历的点一定不能与先遍历的点连边。

考虑把所有点按 $in$ 升序排序成序列 ${a}$，由于结论 $2$ 此时顺序遍历可以类比为拓扑序中顺序遍历。此时若 $\dfrac{N(N-1)}{2}=\sum\limits_{i=1}^N in_{a_i}$，此时产生了一个新的强联通分量拓扑序遍历前缀。

考虑上一个满足条件的是 $N'$，初始 $N'=0$。则 $S=\{a_x:x\in(N',N]\}$ 构成了一个新的强联通分量。由于拓扑序这样显然是不重不漏的。