题解：P3561 [POI 2017] Turysta
这篇题解并不是完整的题解，只是给方法的一种补充。
这里主要给出一个竞赛图哈密顿通路新的构造思路。（自己想的时候想到的，私认为更人类一些）
理论基础基于结论：竞赛图缩完点是一条链。
还有一个结论就是所有点中入度最小的点一定在缩完点后的链的开头（因为对于中间的每一个 SCC 中的每一个点都至少有链前面每个 SCC 的每个点的连边，而 SCC 内部的贡献一定小于 SCC 的大小。所以最小的一定在链的开头。
考虑类似欧拉路径一样 DFS。显然的一点是我们必须在链的开头的 SCC 中选一个点开始。（我们可以直接选入度最小的点）
然后把当前点删掉（即更新入度），然后找当前点能到达的入度最小的点。
一直下去走出来的就是一条通路。
证明的话你考虑：我们走一个点相当于把这个点删掉了（不能走），然后竞赛图删掉一个点后一定还是竞赛图。这是一个子问题。我们每一次走能走的入度最小的点相当于在删掉点的竞赛图上缩完点的链上的开头的 SCC 选了一个点。
但一个问题在于为什么当前点一定能到达链开头 SCC 的一个点。
我们只考虑删点之前当前点所在 SCC。 因为如果把这个点删了，有可能会把当前点所在 SCC 裂成好几个 SCC（如果没有裂开，则缩完点后的图不变，显然可以到达）。SCC 之间是链状的，然后但因为原来是个 SCC，删完不是了，所以一定是链后面的 SCC 经过了当前点到达了链前面的 SCC，也就是说当前点一定能到达链开头的那个 SCC。