NOIP2024集训Day49 图论
NOIP2024集训Day49 图论
A. [BZOJ2348 中山市选2011] 杀人游戏
最优决策一定是我们找到一个点，使它能够尽可能到达更多的点，然后我们会发现必须询问的人缩点后就是入度为 \(0\) 的点。如果剩下了一个人，那么这个人是可以被推出来的。
即：入度为 \(0\) 的点是一定要被询问的，如果存在一个入度为 \(0\) 的点，它的 \(size=1\) 并且到达所有点的入度 \(\gt 1\)，这个点是可以被推出来的。
B. [POI2006] PRO-Professor Szu
先将边反向，这样就变成了从主楼到其他楼的路径数。
然后 Tarjan 求强连通分量。发现一个强连通分量内又多于两个点显然不行。
其他的拓扑排序就好。