在有向无环图上预测路径
我遇到了一个问题，想知道是否有可能预测最终结果。
它是图形（有向无环图）上的一对一（交替移动）游戏。
玩家1从起点或节点开始，选择节点v1的边缘。播放器2从节点v1拾取到节点v3的边缘，依此类推。
取胜方法：一个到达节点且没有边缘损失的玩家。
是否有可能提出一种算法，无论其他玩家做什么，都能保证获胜？
因此，起始节点是s。玩家1可以选择C或A。因此，从根本上来说，我是否有办法基于某种可以保证获胜的算法做出决定？
在这种情况下，如果我位于节点D或B并选择到达节点E的边缘，我将获胜，因此玩家2被卡在节点E上。
*距离无关紧要
您需要将图的节点分为两种类型：获胜节点和败失节点。获胜节点是当前玩家在该节点上具有获胜策略的节点，而失败节点则是无论其玩法如何（假设对手正确玩法），当前玩家都会输掉的节点。由于这是有向无环图，因此所有节点都将赢或输（因为最终将到达一个没有出站边的节点）。
没有输出边缘的节点显然会丢失节点。对于另一个节点N：
- 如果存在从N到丢失节点的一条边，则N是获胜节点。
- 否则，N是一个失败的节点。
要对所有节点进行分类，请按相反的拓扑顺序遍历节点。根据上述规则对每个节点进行分类。反向拓扑顺序可确保在对N进行分类之前，已对可以从N到达的所有节点进行了分类。
完成后，如果起始节点是获胜节点，那么就有一个获胜策略：始终选择失败节点的优势。