写一下思路好了:
- 必须存在一些环才能无限走下去
- 那么最大总数量就是所有环上的节点数量
- 最大黑点数量就是环上的黑点数量+能走到环上白点处的环外黑点数量
- 判环的手段很多,难点在于统计那些黑点
- 注意到至多经过 \(n\times m\) 的时间,环外的点一定能走到环上
- 那么直接看 \(n\times m\) 的时间后这些点走到哪里去了
- 对于这些终点进行统计,讨论它们的源点的颜色
- 复杂度可以用倍增优化到 \(O(nm\log(nm))\)
代码实现的时候注意空间消耗。套多层 vector
容易 MLE。