TIOJ 1092 . A.跳格子遊戲

http://tioj.ck.tp.edu.tw/problems/1092

這是一題需要靈活思考的輕鬆小品~我們定義兩種情況，一個點要嗎必勝不然就必敗，可以發現，要是一個點接下來可以跳的點中，只要有一個是必勝的話，那這個點一定必敗，因為對手下一步一定會選擇到必勝的點，另一方面，如果一個點是必勝的話，那麼接下來可以跳的點一定都是必敗，才能保證這個點是必勝的。因為可以確定終點是必勝的，所以我們可以反向來做，從終點推到起點，由於題目保證圖是一個DAG(有向無環圖)，所以這個順序其實就是這個DAG的拓樸排序。