竞赛图

简介

大概不算是冷门知识吧 = =

性质

1. 竞赛图强连通缩点后的 $DAG$ 呈链状, 前面的所有点向后面的所有点连边

   证明 :

   考虑归纳，逐连通块加入
   目前有一条链，插入一个新连通块 $x$
   如果 $x$ 连向所有点，放在链头
   如果所有点连向 $x$ ，放在链尾
   否则x的出边一定都在 $x$ 的入边的后边 (否则成环)
   找到分界点，把 $x$ 插在中间即可

2. 属于拓扑序较小的强连通分量的中点的入度严格小于拓扑序较大的强连通分量中的点的入度

   证明：

   由 $1$ 易得