【刷题记录】CF 交互构造题

CF 1779 E

给一张竞赛图，问一个 \(n-1\) 场淘汰赛之后可能的冠军有哪些。

通过交互得到竞赛图的度。然后运用竞赛图的一些性质：

1. 可能的冠军 \(u\) 能够到达其他所有节点；

2. \(1\) 的推论，所有可能的冠军节点构成强连通分量；

3. 竞赛图缩点后拓扑序唯一（即呈链状）；

4. 将入度从小到大排序后，若前 \(m\) 个点的入度之和为 \(\dfrac{m(m-1)}{2}\)，则这 \(m\) 个点构成第一个 SCC。

然后就结束了。