Sleepy Game [Codeforces Round #467 (Div. 1) B]

http://codeforces.com/contest/936/problem/B

N頂点M辺の有向グラフがある。
最初に頂点Sに石を置いて、順番に石を辺に沿って動かしていく。
動かせなくなったら負け。
10^6回動かすとその時点であいこになる。
　
「両者が最適に動くとは限らない」とき、先攻の勝敗を答えよ。
先攻が勝つ場合がある場合は"Win"とその経路を答える。
先攻が勝つ場合が無いが、あいこになる場合があるなら"Draw"
先攻がどうやっても負けるしか無いときは"Lose"

解法

http://codeforces.com/contest/936/submission/35718231

後退解析っぽくdfsで解いていく。
「dfs(cu, turn) := 頂点cuに石があり、turnの順番の時の先攻の勝敗」を作る。
minimaxのようにturnの勝敗ではなく、先攻の勝敗であるのに注意。
　
遷移先が無い場合は、そこで終了なので、勝敗が決定する。
turn=0なら負けなので-1
turn=1なら勝ちなので1
　
遷移先がある場合は全ての遷移先を試す。
1つでも勝ち状態があれば、勝ちなので1
勝ち状態が1つも無いが、あいこ状態が1つでもあればあいこにできるので0
全て負けなら-1
　
問題はループが存在することであるが、既に訪れたことがある頂点に来た場合に…
勝敗が確定している → その勝敗を答える
勝敗が確定していない → 永遠と勝敗を先延ばしにできるので、あいことして答える（=0）
　
勝ちの時の経路は1を返す時に記録していけばいい。

int N, M, S;
vector<int> E[101010];
//---------------------------------------------------------------------------------------------------
// -1=lose, 0=draw, 1=win (for me)
vector<int> route;
int vis[101010][2], memo[101010][2];
int dfs(int cu, int turn) {
    if (vis[cu][turn]) return memo[cu][turn];
    vis[cu][turn] = 1;

    int res = 0;
    if (E[cu].size() == 0) {
        if (turn == 0) res = -1;
        else {
            route.push_back(cu + 1);
            res = 1;
        }
    } else {
        int candraw = 0;
        fore(to, E[cu]) {
            int res = dfs(to, 1 - turn);
            if (res == 1) {
                route.push_back(cu + 1);
                return memo[cu][turn] = 1;
            }
            else if (res == 0) candraw = 1;
        }

        if (candraw) res = 0;
        else res = -1;
    }

    return memo[cu][turn] = res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) {
        int C; cin >> C;
        rep(j, 0, C) {
            int x; cin >> x; x--;
            E[i].push_back(x);
        }
    }
    cin >> S; S--;

    int res = dfs(S, 0);

    if (res < 0) printf("Lose\n");
    else if (res == 0) printf("Draw\n");
    else {
        printf("Win\n");
        int n = route.size();
        reverse(all(route));
        rep(i, 0, n) {
            if (i) printf(" ");
            printf("%d", route[i]);
        }
        printf("\n");
    }
}